[자료구조/알고리즘] 우선순위 큐 Priority Queue (Heap) - 파이썬

 우선순위 큐는 내부적으로 이진트리형태의 힙이라는 자료구조로 동작한다. 

 

이진트리 형태

우선순위 큐는 최상단 트리에 있는 요소에 가장 큰 수가 오면 max-heap, 가장 작은 수가 오면 min-heap 이라고 한다. C++에서는 max-heap을 지원하고 파이썬에서는 min-heap을 지원한다. max-heap인 경우 pop()을 했을 때 모든 노드들 중에서 가장 큰 값을 뽑아낸다고장담할 수 있다. min-heap의 경우 반대로 항상 작은 값이 나오게 된다. 이 땐 heappop()을 한다. 

 

 

import heapq 

pq = [] 

heapq.heappush(pq, 456)      # 노드의 맨 뒤에 값을 추가한다
heapq.heappush(pq, 123)
heapq.heappush(pq, 789)
print("size:", len(pq))

while len(pq) > 0:
    print(heapq.heappop(pq))    # 최상단 노드의 값을 하나 뺀다

heapq 모듈 사용하기 

 파이썬에서 우선순위 큐 사용을 위해선 heapq 모듈을 사용한다. 파이썬에서는 min-heap을 지원하기 때문에 가장 작은 값인 123부터 출력되게 된다. 

 

heappush(), heappop()

큐가 알아서 순서배치를 해준다. 테스트해보니 꼭 순서대로 배치해두진 않는다. [-5, 0, 6, 12, 8] but 0번째 인덱스에는 항상 최상단 루트 노드가 온다. 최상단 노드가 중요하다. 그 외의 순서는 그닥 고려하지 않아도 된다. 

 

from queue import PriorityQueue 

pq = PriorityQueue()
pq.put(6)
pq.put(10)
pq.put(-5)
pq.put(0)
pq.put(8)

while not pq.empty():
    print(pq.get())   #pop

 파이썬에 우선순위 큐 모델이 존재하지만 속도가 느려 알고리즘에선 쓰지 않는다. 

 

 

 

 

 

시간복잡도 

 위와 같은 이진트리 형태는 시간복잡도를 log2를 갖는 경우가 많다. 우선순위 큐의 삽입/삭제시 시간복잡도는 O(logN)이다. O(N)보다는 빠르고 O(1)보다는 느린 값이다. logN도 효율이 우수한 시간복잡도에 속한다.