[알고리즘] 힙(heap)의 응용: 우선순위 큐(priority queue)

이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요;)

---

우선순위 큐 역시 힙과 같이

최대 우선순위 큐(maximum priority queue)와

최소 우선순위 큐(mininum priority queue)로 나눌 수 있습니다.

 

최대 우선순위 큐는 큐에 저장된 데이터들은 모두 우선순위를 가지고 있고, 이 우선순위가 최대한 데이터들이 큐를 먼저 나갈 수 있습니다. 

큐에 데이터를 저장하는 INSERT(x) 연산에 대해서는 아무 데이터나 상관없지만, 큐를 빠져나가는 EXTRACT_MAX(x) 연산에 대해서는 함수의 이름에서 알 수 있듯이 우선순위가 MAX인 데이터만 이 연산을 진행할 수 있습니다.

 

우선순위 큐의 종류에는 FIFO 큐라는 종류의 큐도 존재합니다.

FIFO 큐란 First In First Out의 약자로 데이터를 담는 큐에 가장 먼저(Fisrt) 들어온 데이터가 큐를 빠져나갈 때에도 가장 먼저(First) 나간다는 의미입니다. 즉 FIFO 큐에서는 들어온 순서가 곧 우선순위라고 생각하면 될 것 같습니다.

---

MAX Heap의 조건

1) Complete binary tree -> tree의 마지막 레벨의 오른쪽 끝부터 연속적으로 노드가 비어있거나 완전히 트리가 꽉 차야 하고

2) 부모 노드가 자식노드보다 커야 함

 

이러한 MAX Heap의 조건을 유지해야 하기 때문에 아무 자리에나 자식 노드를 추가할 수 없고, 오직 (b)에서 15가 추가된 자리 즉, 일차원 배열의 마지막 자리에만 추가할 수 있습니다. 

이렇게 데이터를 추가하면 complete binary tree의 모양은 유지할 수 있지만, MAX Heap property의 조건 중 2번, 그러니까 부모 노드가 자식 노드보다 큰 값을 가져야 한다는 조건이 흐트러집니다.

때문에 추가한 15를 자신의 부모 노드와 비교해서 만약 부모노드보다 크다면 부모 노드와 자리를 바꿔갑니다. 같은 부모 노드를 두고 있는 또 다른 자식 노드의 입장에서는, 원래 자신보다 값이 컸던 부모 노드보다 큰 값의 노드가 새로운 부모 노드로 오는 것이기 때문에 Max heap property가 흐트러질 걱정을 할 필요가 없습니다.

이진(binary) 트리의 층이 곧 시간복잡도이기 때문에 lg2가 INSERT의 시간 복잡도입니다.

---

최대 우선순위 큐는 값이 가장 큰 값, 즉 큐의 루트 노드가 가장 우선적으로 큐를 빠져나가 수 있기 때문에 일단 루트 노드가 큐에서 제외됩니다. 그다음이 문제인데, HEAP의 조건이 Complete binary tree를 유지하기 위해선 사라진 루트 노드의 자리에 큐의 가장 마지막 노드, 일차원 배열로 치면 가장 마지막 데이터를 루트 노드의 자리에 옮겨줍니다. 

하지만 이렇게 되면 역시 heap property가 흐트러지기 때문에, 바뀐 루트 노드의 값을 자식 노드들과 비교하며 heap property를 만족시킬 수 있는 위치로 이동시켜줍니다. 즉 루트 노드에 대해, 두 개의 자식 노드 중 더 큰 자식 노드가 자신보다 크다면 그 노드와 자신을 바꾸는 max-heapify를 진행하며 tree 전체의 heap property를 만족시켜줍니다.

힙의 크기를 줄여주는 건, 힙 배열의 크기를 1 줄여주면 됩니다. 이 작업 역시 heapify 작업을 진행하기 때문에 EXTRACT_MAX의 시간 복잡도도 lg2입니다.