우선순위 큐 (Priority Queue)

정의

우선순위 큐 (Priority Queue) 는 원소 중 최댓값 (또는 최솟값) 을 O(log N) 에 추출하는 자료구조. 내부 구현은 대개 힙 (heap).

• Max-Heap: 부모 ≥ 자식. 루트가 최댓값.
• Min-Heap: 부모 ≤ 자식. 루트가 최솟값.

C++ STL std::priority_queue 는 기본 max-heap. Python heapq 는 기본 min-heap.

문제 상황과 동기

“항상 최댓값 (또는 최솟값) 을 빠르게 꺼내야” 하는 상황:

• naive: 정렬 후 꺼낸다. 삽입마다 정렬 O(N log N), 쿼리 O(1). 삽입 많으면 비효율.
• 정렬 없이 최댓값: 선형 탐색 O(N). 쿼리가 Q 개면 O(N·Q).
• priority queue (heap): push O(log N), pop O(log N), top O(1). 삽입 + 추출 모두 로그.

핵심 통찰: 트리 구조 (부모 ≥/≤ 자식) + 완전 이진 트리 + 배열 표현 → 삽입/삭제 모두 O(log N), 캐시 친화적.

시각화

핵심 아이디어

힙은 완전 이진 트리 (complete binary tree) 로, 배열에 저장:

인덱스 i 노드의 부모: (i-1)/2  (0-indexed)
왼쪽 자식: 2i+1
오른쪽 자식: 2i+2

Max-Heap invariant: a[parent] ≥ a[child] 모든 부모-자식 쌍에서 성립.

연산

1. push(x) (upheap / bubble-up):

   • 배열 끝에 x 추가.
   • 부모와 비교, 크면 swap. 루트 또는 부모 ≥ x 될 때까지 반복.
   • O(log N).

2. pop() (downheap / bubble-down):

   • 루트 제거 (최댓값).
   • 배열 마지막 원소를 루트로 올림.
   • 두 자식 중 큰 쪽과 비교, 작으면 swap. 자식 없거나 자식 ≤ 현재값 될 때까지 반복.
   • O(log N).

3. top(): 배열 첫 원소 (루트). O(1).

Amortized analysis: 각 원소가 트리 높이 log N 만큼만 이동. N 번 push + N 번 pop 총 O(N log N).

알고리즘

push(x):
    arr.append(x)
    i = len(arr) - 1
    while i > 0 and arr[parent(i)] < arr[i]:
        swap(arr[i], arr[parent(i)])
        i = parent(i)

pop():
    max_val = arr[0]
    arr[0] = arr.back()
    arr.pop_back()
    i = 0
    while True:
        left = 2*i + 1, right = 2*i + 2
        largest = i
        if left < len(arr) and arr[left] > arr[largest]:
            largest = left
        if right < len(arr) and arr[right] > arr[largest]:
            largest = right
        if largest == i:
            break
        swap(arr[i], arr[largest])
        i = largest
    return max_val

top():
    return arr[0]

구현

// C++ std::priority_queue (max-heap 기본)
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n; cin >> n;
  priority_queue<int> pq; // max-heap
  for (int i = 0; i < n; i++) {
      int x; cin >> x;
      pq.push(x);
  }
  // 최댓값부터 순서대로 pop
  while (!pq.empty()) {
      cout << pq.top() << " ";
      pq.pop();
  }
}

# Python heapq (min-heap 기본, max-heap 은 음수 저장)
import heapq
import sys
input = sys.stdin.readline
​
n = int(input())
pq = []
for _ in range(n):
  x = int(input())
  heapq.heappush(pq, -x)  # 음수로 저장 (max-heap 흉내)
ans = []
while pq:
  ans.append(-heapq.heappop(pq))
print(" ".join(map(str, ans)))

// Java PriorityQueue (기본 min-heap, Comparator 로 max-heap)
import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine());
      PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); // max-heap
      for (int i = 0; i < n; i++) {
          pq.offer(Integer.parseInt(br.readLine()));
      }
      StringBuilder sb = new StringBuilder();
      while (!pq.isEmpty()) {
          sb.append(pq.poll()).append(" ");
      }
      System.out.println(sb);
  }
}

5
3
1
4
1
5

5 4 3 1 1

복잡도

변형 / 활용

함정

1. C++ vs Python 기본 순서

C++ priority_queue 는 max-heap. Python heapq 는 min-heap. 혼동 주의.

Python 에서 max-heap 은 heappush(pq, -x), heappop(pq) 후 - 붙여 원복.

2. Java PriorityQueue 는 기본 min-heap

max-heap 은 new PriorityQueue<>(Collections.reverseOrder()) 또는 (a, b) -> b - a.

3. top 후 pop 안 하기

top 은 값만 확인. 제거는 pop. 둘 다 해야 한다.

4. 중복 원소

힙은 중복을 허용. 같은 값 여러 개 push 가능. 필요시 set 과 함께 써서 중복 제거.

5. 힙 정렬 (Heap Sort) 은 O(N log N) 이지만 캐시 비효율

같은 O(N log N) 이어도 quick sort / merge sort 가 일반적으로 빠름. 힙은 주로 “부분 정렬” (top K) 에 쓴다.

BOJ 연습 문제

참고

• 힙
• Dijkstra
• 최소 신장 트리
• Top K