힙(Heap) & 우선순위큐(Priority Queue) 의 구현과 성질

 힙(Heap)은 특정 연산을 빠르게 수행하기 위한 이진 트리 자료 구조로 부모 노드와 자식 노드간의 일련의 규칙을 통해 일관성있는 결과를 도출해내기 위한 자료구조이다. 

 가령 Min Heap 이라함은 부모가 자식보다 작은 이진 트리를 구성하며 루트노드가 즉 전체 데이터의 최솟값이 된다. 반대로 Max Heap 은 부모가 자식보다 큰 자료구조이기 때문에 루트노드는 전체 데이터의 최댓값을 나타낸다.

 Binary Heap 을 구현할 경우 이진 트리의 Root 노드부터 단일 Leaf 노드까지의 순회비용만 가질 뿐이므로 Insert 와 Delete 연산이 모두 O(logN) 의 복잡도를 갖으며 Min Heap / Max Heap 과 같은 기능적 힙을 구현하는 경우 (아마 대부분의 경우), 조회(Peek) 의 시간 복잡도는 O(1) 로 아주 효율적이다.

다음은 Binary Heap 의 배열을 이용한 예시의 그림이다. 

<Binary Heap 에서 Push 의 Work flow>

 Binary Heap 에서 새로운 값을 Push 할 때에는 Heap 의 마지막 위치(Leaf Node)에 값을 넣고, 루트 노드(Root Node) 까지 올라오면서 맞는 위치를 찾는다.

Min Heap 이냐 Max Heap 이냐에 따라서 조건에 만족한다면 해당 위치에 멈추고, 더 위쪽 노드로 가야한다면 부모노드와 Swap 해준다. 자매 노드(Siblings) 를 고려하지 않아도 되기 때문에 구현은 편안하다.

<Binary Heap 에서 Pop 의 Work flow>

 Pop 연산은 이와 반대로 구현된다. 특성상 무조건 Root Node 에 원하는 값이 있다. Min Heap 의 경우 데이터 전체의 최솟값이, Max Heap 의 경우 데이터 전체의 최댓값이 있다.

따라서 꺼내오는 시간은 O(1) 이며, 대신 꺼낸 자리에 Leaf Node 로 보낼 값을 집어넣는다. Min Heap의 경우 최댓값을 넣어 무조건 맨 끝으로 보낼 수 있게 한다. 그리고 나서는 왼쪽 자식(Left) 과 오른쪽 자식(Right) 을 비교하여 더 작거나(Min) 더 큰(Max) 값과 부모의 값을 교환하면서 내려간다.

이에 대한 자세한 구현은 다음 코드를 참조하자. C 로 구현되어있으나 어렵진 않을 것이다.

int h[1501] = {0, };

int hn=0;

void push(int x)

{

int cur = hn;

h[hn++] = x;

while(cur > 0)

{

int parent = (cur-1)/2;

if(h[parent] > h[cur]) {

swap(h[parent], h[cur]);

} else {

break;

}

cur = parent;

}

}

int pop()

{

int ret = h[0];

h[0] = 1e8;

swap(h[0], h[--hn]);

int cur = 0;

while(2*cur+2 <= hn)

{

int l=2*cur+1, r=2*cur+2;

int nxt = h[l] < h[r] ? l : r;

if(h[nxt] < h[cur])

{

swap(h[nxt], h[cur]);

cur = nxt;

}

else

{

break;

}

}

return ret;

}

이처럼 힙은 데이터를 다루고 관리하는 유용한 자료구조이며 이 자료구조를 응용한 대표적인 사례가 우선순위큐(Priority Queue) 이다. 가령 각 노드별로 우선순위를 기록하고, 모든 노드의 우선순위(1~N) 대로 Min Heap 을 구성한다면 우선순위의 Ordering 이 낮은 순서대로 데이터를 뽑아낼 수 있다.

우선순위큐는 우선순위를 순차적으로 뽑아낼 수 있는 Push / Pop 이 가능한 자료구조일 뿐 그 구현이 Heap 일 필요는 없지만, 보통 Heap 을 이용해서 구현할 경우 Push 와 Pop 에 O(logN) 이라는 저렴한 시간복잡도가 들기 때문에 주로 Heap으로 구현이 된다.

즉, Priority Queue 를 Heap 을 이용해 만들 수 있지만 Heap 과 Priority Queue 간에는 직접적인 연관은 없으며 다만 구현에 있어서도, 기능에 있어서도 Heap 을 이용해 만드는 것이 효과적이므로 거의 동일어나 다름없이 혼용되고 있을 뿐이다.

각종 기업 면접과 테스트에서 코딩 테스트라 불리는 알고리즘 역량이 상당히 중요해진 만큼, 연습하는데 있어서 정말 유용한 자료구조이니, 위의 코드는 외워두고 써도 좋다.