우선 순위 큐(heap)

큐 : FIFO 구조로 들어온 순서대로(enqueue) 나가는(dequeue) 자료구조이다.

우선 순위 큐 : 우선 순위가 높은 것이 먼저 나가는 자료구조이다.

 

우선 순위 큐를 구현하는 방법은 다양하지만 그 중 heap 이라는 자료구조에서 enqueue, dequeue하는 방법이 가장 시간이 적게 걸린다.

 

heap

완전 이진 트리 형태로 우선 순위 큐를 구현하기 위해 만들어진 자료구조이다.

 

✔ min heap(최소 힙)

"부모 노드 < 자식 노드" 인 완전 이진 트리

✔ max heap(최대 힙)

"부모 노드 > 자식 노드" 인 완전 이진 트리

 

Enqueue와 Dequeue

min heap 자료구조를 바탕으로 설명하겠습니다.

"우선 순위가 높다"는 것은 숫자가 더 작다는 의미

 

[Enqueue]

1) 새로운 노드를 마지막 노드에 추가

2) 부모 노드와 우선순위를 비교하여 높은 것을 위로 올리기 (Bubble Up)

 

[Dequeue]

1) 루트 노드를 제거 (Pop)

2) 마지막 노드를 루트로 이동

3 ) 루트 노드부터 자식 노드와 비교하여 자식 노드가 우선순위가 더 높으면 아래로 내리기 (Down heap)

  - 이 때 두개의 자식 노드 중 우선 순위가 더 높은 자식노드와 부모 노드를 비교하게 됩니다.

 

heap 배열

그림에서는 트리 형태로 나타내었지만, 사실 배열로도 나타낼 수 있습니다.

 

arr = [2, 3, 5, 8, 9, 6, 1] 로 나타낼 수 있습니다.

 

✔ 삽입 연산 시(Enqueue)

자식 노드가 i 라면 i //2와 우선 순위를 비교합니다.

 - 자식 노드 : i 

 - 부모 노드 : i // 2

 

✔ 삭제 연산 시(Dequeue)

부모 노드가 i 라면 min(i*2, i*2+1) 과 우선 순위를 비교합니다.

 - 부모 노드 : i 

 - 자식 노드 : min(i*2, i*2+1)

 

파이썬 heap

import heapq

min_heap = [5, 3, 9, 4, 1]
heapq.heapify(min_heap)
print(min_heap) # [1, 3, 9, 4, 5]
min_val = heapq.heappop(min_heap)
print(min_val, min_heap) # 1 [3, 4, 9, 5]

 

⭐ 주의할 점

파이썬 내장함수 heapify는 자식의 순서를 보장하지 않습니다.

실제로 그림을 그려서 해보면 [1, 3, 9, 5, 4] 이지만 내장함수로 돌렸을 때 자식 노드 4, 5의 위치가 바뀐것을 확인할 수 있습니다.

import heapq

arr = [5, 3, 9, 4, 1]
min_heap = []
for s in arr:
    heapq.heappush(min_heap, s)

print(min_heap) # [1, 3, 9, 5, 4]

 

시간복잡도

✔ heapify => O(n)

✔ heappush => O(logn)

✔ heappop => O(logn)