[자료구조] 힙(Heap)과 우선순위 큐(Priority Queue) - 코딩밥상

힙(Heap)이란?

힙은 순서 속성(Heap Order Property)을 만족하는 완전 이진 트리입니다.

완전 이진 트리를 복습하자면, 최고 깊이를 제외한 모든 깊이의 노드가 완전히 채워져있는 트리입니다. '힙 순서 속성'이란 트리 내의 모든 노드가 부모 노드보다 커야 한다는 규칙입니다. (본 정리 글에서는 정수 데이터 값을 priority기준으로 하겠습니다.) 

힙은 이진 탐색이 불가능하기에 모든 노드를 순회하며 탐색해야 합니다. 하지만 "힙에서 가장 작은 데이터를 갖는 노드는 뿌리 노드이다" 라는 규칙을 가집니다.

따라서 힙에 사용되는 연산은 두 가지뿐입니다

• 노드 삽입 연산
  1. 힙의 최고 깊이 가장 우측에 새 노드를 추가(완전 이진 트리 유지)
  2. 삽입한 노드를 부모 노드와 비교 - 부모 노드보다 크면 종료, 작으면 3단계 이동
  3. 삽입한 노드가 부모 노드보다 작으면 부모 노드와 삽입한 노드를 스왑, 2단계 다시 진행

=> 새로 삽입한 노드가 힙 순서 속성을 만족할 때까지 삽입한 노드와 부모 노드를 교환

• 최솟값 삭제 연산(뿌리 노드 삭제 연산)
  1. 뿌리 노드 삭제 
  2. 힙의 최고 깊이 가장 우측에 있던 노드를 뿌리 노드로 옮김
  3. 옮겨온 노드(새로 온 뿌리 노드)와 양쪽 자식 노드를 비교하여 작은 값과 스왑
  4. 옮겨온 노드가 더 이상 자식이 없는 잎 노드로 되거나 양쪽 자식보다 작은 값을 갖는 경우 삭제 연산 종료, 그렇지 않으면 3번부터 반복  

=> 최솟값 노드(뿌리 노드) 삭제 후 마지막 노드를 뿌리노드로 올리고 그 노드가 맞는 자리로 갈 때까지 자식 노드와 교환

---

힙 구현

힙은 완전 이진 트리이기에 배열을 이용하여 구현하면 다음과 같은 규칙으로 완전 이진 트리를 나타낼 수 있습니다.

깊이 0의 노드는 배열 0번 인덱스에 저장 -> 깊이 1의 노드는 배열 1~2번 인덱스에 저장 -> 깊이 2의 노드는 배열 3~6번 인덱스에 저장

-> 깊이 n의 노드는 배열 2^n-1 ~ 2^n*2-2번 인덱스에 저장

 

이 규칙을 따르면 다음과 같이 각 노드의 양쪽 자식 노드들의 인덱스도 규칙을 찾을 수 있습니다.

k번 인덱스에 위치한 노드의 양쪽 자식 노드들이 위치한 인덱스

-왼쪽 자식 노드 : 2k+1

-오른쪽 자식 노드 : 2k+2

k번 인덱스에 위치한 노드의 부모 노드가 위치한 인덱스 : (k-1)/2의 몫

 

구조체 

typedef int ElementType;

typedef struct tagHeapNode{ //노드 구조체
    ElementType Data;
} HeapNode;

typedef struct tagHeap{ //힙 구조체
    HeapNode* Nodes;
    int Capacity;   //용량
    int UseSize;    //실제 배열 안에 들어있는 큐의 수
} Heap;

삽입 연산

void HEAP_Insert(Heap* H, ElementType NewData){
    int CurrentPosition = H->UseSize;
    int ParentPosition = HEAP_GetParent(CurrentPosition);
    
    if(H->UseSize == H->Capacity){  //용량이 다 차면 기존 용량의 2배로 만듦 
        H->Capacity *= 2;
        H->Nodes (HeapNode*)realloc(H->Nodes, sizeof(HeapNode) * H->Capacity);
    }
    
    H->Nodes[CurrentPosition].Data = NewData;
    
    while(CurrentPosition>0 && H->Nodes[CurrentPosition].Data<H->Nodes[ParentPosition].Data){   //후속 처리(부모 노드와 비교 후 더 작으면 스왑)
        HEAP_SwapNodes(H, CurrentPosition, ParentPosition);
        
        CurrentPosition = ParentPosition;
        ParentPosition = HEAP_GetParent(CurrentPosition);
    }
    
    H->UseSize++;
}

최솟값(뿌리 노드) 삭제 연산

void HEAP_DeleteMin(Heap* H, HeapNode* Root){
    int ParentPosition = 0;
    int LeftPosition = 0;
    int RightPosition = 0;
    
    memcpy(Root, &H->Nodes[0], sizeof(HeapNode));   //Root에 최솟값 저장
    memset(&H->Nodes[0], 0, sizeof(HeapNode));
    
    H->UseSize--;
    Heap_SwapNodes(H, 0, H->UseSize);   //힙의 첫 인덱스에 마지막 인덱스 값을 복사(마지막 요소를 루트로 옮김)
    
    LeftPosition = HEAP_GetLeftChild(0);
    RightPosition = LeftPosition + 1;
    
    while(true){
        int SelectedChild = 0;
        
        if(LeftPosition >= H->UseSize) break;	//자식 노드가 없는 경우(leaf노드 까지 교환한 경우) 
        
        if(RightPosition >= H->UseSize){
            SelectedChild = LeftPosition;
        }
        else{
            if(H->Nodes[LeftPosition].Data > H->Nodes[RightPosition].Data)
                SelectedChild = RightPosition;
            else
                SelectedChild = LeftPosition;
        }
        
        if(H->Node[SelectedChild].Data < H->Nodes[ParentPosition].Data){	//선택한 노드보다 부모 노드가 크다면 스왑
            HEAP_SwapNodes(H, ParentPosition, SelectedChild);
            ParentPosition = SelectedChild;
        }
        else break;
        
        LeftPosition = HEAP_GetLeftChild(ParentPosition);
        RightPosition = LeftPosition + 1;
    }
    
    if(H->UseSize < H->Capacity/2){ //낭비되는 공간 줄여줌
        H->Capacity /= 2;
        H->Nodes = (HeapNode*)realloc(H->Nodes, sizeof(HeapNode)*H->Capacity);
    }
}

 

그 외 보조 연산들

void HEAP_SwapNodes(Heap* H, int index1, int index2){
    int CopySize = sizeof(HeapNode);
    HeapNode* Temp = (HeapNode*)malloc(CopySize);
    
    memcpy(Temp, &H->Nodes[index1], CopySize);
    memcpy(&H->Nodes[index1], &H->Nodes[index2], CopySize);
    memcpy(&H->Nodes[index2], &H->Nodes[index1], CopySize);
    
    free(Temp);
}

int HEAP_GetLeftChild(int index){
    return (2*index) + 1;
}
int HEAP_GetParent(int index){
    return (int)((index - 1)/2);
}

---

 

우선순위 큐(Priority Queue)란?

속성을 갖는 데이터의 삽입과 제거 연산을 지원하는 ADT입니다.

우선순위 큐와 보통 큐의 차이는 삽입과 제거 연산이 '어떻게 동작 하는가?'에 있습니다. 보통 큐는 먼저 들어온 요소가 무조건 먼저 나오게 되지만, 우선순위 큐는 새 요소에 우선순위를 부여해서 큐에 삽입하고 가장 높은 우선순위를 가진 요소부터 빠져나오게 됩니다.

 

즉 힙은 최솟값(또는 최댓값)을 즉시 얻어낼 수 있기때문에 우선순위 큐의 삭제 연산(Dequeue)의 구현 방법에 용이하고,

힙의 삽입 연산은 마지막 단에서부터 하나씩 올라가며 자신의 위치에 맞는 인덱스로 찾아 들어가기때문에 우선순위의 삽입 연산(Enqueue)의 구현에 용이합니다

따라서 힙의 삽입(Insert),삭제(Delete) 연산은 우선순위 큐의 삽입(Enqueue),삭제(Dequeue) 연산과 같은 알고리즘으로 구현할 수 있는 것입니다.

---

힙 기반 우선순위 큐 구현

삽입 연산

void PQ_Enqueue(PriorityQueue* PQ, PQNode NewNode){
    int CurrentPosition = PQ->UseSize;
    int ParentPosition = PQ_GetParent(CurrentPosition);
    
    if(PQ->UseSize == PQ->Capacity){  //용량이 다 차면 2배 들림
        if(PQ->Capacity == 0)
            PQ->Capacity = 1;
        
        PQ->Capacity *= 2;
        PQ->Nodes = (PQNode*) realloc(PQ->Nodes, sizeof(PQNode)*PQ->Capacity);
    }
    
    PQ->Nodes[CurrentPosition] = NewNode;
    
    while(CurrentPosition > 0 && PQ->Nodes[CurrentPosition].Priority < PQ->Nodes[ParentPosition].Priority){   //후속 처리(부모 노드와 비교 후 더 작으면 스왑)
        PQ_SwapNodes(PQ, CurrentPosition, ParentPosition);
        
        CurrentPosition = ParentPosition;
        ParentPosition = PQ_GetParent(CurrentPosition);
    }
    
    PQ->UseSize++;
}

삭제 연산

void PQ_Dequeue(PriorityQueue* PQ, PQNode* Root){
    int ParentPosition = 0;
    int LeftPosition = 0;
    int RightPosition = 0;
    
    memcpy(Root, &PQ->Nodes[0], sizeof(HeapNode));   //Root에 최솟값 저장
    memset(&PQ->Nodes[0], 0, sizeof(HeapNode));
    
    PQ->UseSize--;
    PQ_SwapNodes(PQ, 0, PQ->UseSize);   //힙의 첫 인덱스에 마지막 인덱스 값을 복사(마지막 요소를 루트로 옮김)
    
    LeftPosition = PQ_GetLeftChild(0);
    RightPosition = LeftPosition + 1;
    
    while(true){
        int SelectedChild = 0;
        
        if(LeftPosition >= PQ->UseSize) break;  //선택 노드의 자식이 없는 경우 종료
        
        if(RightPosition >= PQ->UseSize){   //선택 노드의 자식이 있는 경우
            SelectedChild = LeftPosition;
        }
        else{
            if(PQ->Nodes[LeftPosition].Priority > PQ->Nodes[RightPosition].Priority)    //자식 노드 중 우선 순위가 더 작은 노드가 비교 대상이 됨
                SelectedChild = RightPosition;
            else
                SelectedChild = LeftPosition;
        }
        
        if(PQ->Nodes[SelectedChild].Priority < PQ->Nodes[ParentPosition].Priority){ //선택된 노드와 부모 노드를 비교하여 조건에 맞게 스왑
            PQ_SwapNodes(PQ, ParentPosition, SelectedChild);
            ParentPosition = SelectedChild;
        }
        else break;
        
        LeftPosition = PQ_GetLeftChild(ParentPosition); //부모 노드를 기준으로 조건에 맞을때 까지 수행
        RightPosition = LeftPosition + 1;
    }
    
    if(PQ->UseSize < PQ->Capacity/2){ //낭비되는 공간 줄여줌
        PQ->Capacity /= 2;
        PQ->Nodes = (PQNode*)realloc(PQ->Nodes, sizeof(PQNode)*PQ->Capacity);
    }
}