[자료구조] 우선순위 큐 (Priority Queue)

- C++은 Max-heap(Root node가 최대값),Python은 Min-heap

- C++은 파이썬과 달리, pop을 해도 반환값이 없다.

- 삽입/삭제 시간복잡도 O(logN)

 

1) C++

priority_queue<int> pq;
pq.push(456);
pq.push(123);
pq.push(789);

printf("size: %d\n",pq.size());
while(!pq.empty()){
	printf("%d\n",pq.top());
	pq.pop();
}

 

2) Python

import heapq

pq = []
heapq.heappush(pq,456)
heapq.heappush(pq,123)
heapq.heappush(pq,789) # [123,456,789]
print("size:",len(pq))
while len(pq)>0:
    print(heapq.heappop(pq))
    
# 결과값--
# 123
# 456
# 789

---

3) Python thread safe(속도느림.HeapQueue 권장)

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
# 결과값 --    
# -5
# 0
# 6
# 8
# 10