자료구조 (우선순위 큐)

우선순위 큐(Priority Queue)

우선순위 큐란 큐처럼 먼저 들어오는 데이터가 아닌 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다

우선순위 큐에 삽입/삭제 속도는 O(log N)이다

우선순위 큐는 Max-Heap 방식과 Min-Heap 방식 둘로 나뉘는데 Max-Heap은 위 그림과 같이 부모 노드의 키 값이 자식 노드보다 크거나 같은 완전이진트리이고 Min-Heap은 그 반대이다

C++ 코드로는 이렇게 구현하며 Max-Heap 방식이다

priority_queue<int> pq;

pq.push(0);
pq.push(1);
pq.push(2);
pq.push(3);

cout << "size: " << pq.size() << "\n";

while (!pq.empty()) {
    cout << pq.top();
    pq.pop();
}

Python 코드로는 이렇게 구현할 수 있으며 Min-Heap 방식이다

import heapq

pq = []

heapq.heappush(pq, 0)
heapq.heappush(pq, 1)
heapq.heappush(pq, 2)
heapq.heappush(pq, 3)

print(f"size: {len(pq)}")

while pq:
    print(heapq.heappop(pq))