Priority Queue / Heap: 우선순위 큐

Priority Queue / Heap, Priority Queue, Heap, 우선순위 큐, 힙, binary heap

정의

Priority Queue 는 우선순위가 가장 높은 원소를 O(log N) 에 pop 할 수 있는 자료구조입니다. Binary Heap 이 표준 구현.

Max-heap: 부모 >= 자식. Min-heap: 부모 <= 자식.

연산:

• push: O(log N)
• top/pop: O(1) / O(log N)
• build_heap: O(N) (heapify)

배열 표현

노드 i 의 부모 = (i-1)/2, 자식 = 2i+1, 2i+2.

priority_queue<int> pq;              // max-heap
priority_queue<int, vector<int>, greater<>> mn;  // min-heap

응용

• Dijkstra 최단 경로 (min-heap 으로 다음 정점 선택)
• Median of Stream (두 heap)
• Top K
• Huffman coding
• Event simulation

변형

• Fibonacci Heap: decrease-key O(1) amortized, 실전 상수 커서 잘 안 씀
• Pairing Heap: 구현 단순, 실전 성능 양호
• Binomial Heap: merge 가 O(log N)

참고

• Dijkstra
• Top K
• Median of Stream