22. 우선순위 큐

우선순위 큐

빠른 설명

우선순위 큐는 가장 우선순위가 높은 원소를 빠르게 꺼내는 자료구조다. 보통 힙(heap)으로 구현한다.

언제 쓰는가

• 항상 가장 작은 값 또는 가장 큰 값을 꺼내야 할 때
• 다익스트라 알고리즘
• 작업 스케줄링
• 중간중간 값이 추가되는 정렬 상황

시간복잡도

• push: $O(\log N)$
• pop: $O(\log N)$
• top 확인: $O(1)$

참고자료

• Wikipedia - Priority queue
• cppreference - std::priority_queue
• Python - heapq
• GeeksforGeeks - Priority Queue

C++ 코드

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
int main() {
    priority_queue<int, vector<int>, greater<int>> pq; // min-heap
 
    pq.push(5);
    pq.push(1);
    pq.push(3);
 
    while (!pq.empty()) {
        cout << pq.top() << ' ';
        pq.pop();
    }
}

Python 코드

import heapq
 
pq = []
heapq.heappush(pq, 5)
heapq.heappush(pq, 1)
heapq.heappush(pq, 3)
 
while pq:
    print(heapq.heappop(pq), end=" ")