우선순위 큐

우선순위 큐란?

우선순위 큐(priority queue) 는 들어온 순서가 아니라 우선순위가 가장 높은
원소가 먼저 나오는 자료구조입니다. 보통 "가장 큰 값" 또는 "가장 작은 값"을
꺼내는 용도로 씁니다.

일반 큐는 FIFO지만, 우선순위 큐는 "가장 중요한 것 먼저"입니다. 응급실에서
도착 순서가 아니라 위급한 환자부터 보는 것과 같습니다.

1. 무엇을 빠르게 해 주나

우선순위 큐의 핵심 연산과 복잡도:

• 삽입(push): \(O(\log N)\)
• 최댓값/최솟값 꺼내기(pop): \(O(\log N)\)
• 최댓값/최솟값 보기(top): \(O(1)\)

정렬 배열에서 매번 최솟값을 꺼내려면 \(O(N)\)이 들지만, 우선순위 큐는 삽입과
삭제를 모두 \(O(\log N)\)에 처리합니다. 동적으로 값이 들어오고 나가며 매번
극값이 필요할 때 최적입니다.

2. 내부 구조: 힙

우선순위 큐는 보통 힙(heap) 이라는 완전 이진 트리로 구현됩니다.

• 최대 힙: 모든 부모가 자식보다 크거나 같다 → 루트가 최댓값.
• 최소 힙: 모든 부모가 자식보다 작거나 같다 → 루트가 최솟값.

배열 하나로 트리를 표현합니다 — 인덱스 \(i\)의 자식은 \(2i+1, 2i+2\), 부모는
\((i-1)/2\). 삽입·삭제 후 부모-자식 관계를 만족하도록 위/아래로 값을 교환
(sift)하며, 트리 높이가 \(\log N\)이라 각 연산이 \(O(\log N)\)입니다.

3. 무엇을 못 하나

우선순위 큐는 극값만 빠르게 줍니다. 다음은 못 합니다.

• 임의 원소 검색/삭제(특정 값 찾기) — 지원 안 함.
• 정렬된 전체 순회 — 하나씩 꺼내면 정렬이 되지만 그땐 구조가 비워집니다.
• "k번째로 큰 값" 직접 조회 — 별도 기법 필요.

"가장 크거나 작은 것 하나"만 반복해서 필요할 때 쓰는 도구임을 기억하세요.

4. 대표 활용

특히 다익스트라에서 우선순위 큐가 핵심 부품이라, Gold 단계로 가는 다리가
됩니다.

5. 힙 정렬로 보는 정당성

모든 원소를 힙에 넣고(\(O(N \log N)\)) 하나씩 꺼내면 정렬된 순서로 나옵니다. 이것이
힙 정렬이며, 우선순위 큐가 "매번 정확히 극값을 준다"는 보장을 확인시켜
줍니다.

정리

우선순위 큐는 힙으로 구현되어, 삽입·극값 삭제를 \(O(\log N)\)에 처리합니다.
"동적으로 들어오고 나가는 값 중 매번 최대/최소가 필요"하면 우선순위 큐입니다.
다익스트라·스케줄링·중앙값 유지의 핵심 부품입니다. 다음 강의에서 코드로 익힙니다.

우선순위 큐를 코드로

언어별 라이브러리 사용법과 대표 응용을 다룹니다.

1. C++ priority_queue

기본은 최대 힙(가장 큰 값이 top)입니다.

#include <queue>
priority_queue<int> pq;          // 최대 힙
pq.push(5); pq.push(1); pq.push(3);
cout << pq.top();                // 5 (최댓값)
pq.pop();                        // 5 제거

최소 힙은 비교자를 바꿔 만듭니다 — 가장 자주 쓰는 관용구입니다.

priority_queue<int, vector<int>, greater<int>> pq;   // 최소 힙
// 또는 음수로 넣었다가 음수로 꺼내는 트릭도 흔함

2. Python heapq (최소 힙)

파이썬 heapq는 최소 힙만 제공합니다.

import heapq
pq = []
heapq.heappush(pq, 5)
heapq.heappush(pq, 1)
smallest = heapq.heappop(pq)     # 1 (최솟값)
peek = pq[0]                     # 꺼내지 않고 최솟값 보기

최대 힙이 필요하면 값에 음수를 붙여 넣고 꺼낼 때 다시 음수를 취합니다.

heapq.heappush(pq, -x)           # 넣을 때 음수
biggest = -heapq.heappop(pq)     # 꺼낼 때 다시 음수

리스트를 한 번에 힙으로 만들려면 heapq.heapify(arr) — \(O(N)\)입니다.

3. 원소가 튜플일 때 (다익스트라 형태)

(거리, 정점)처럼 튜플을 넣으면 첫 번째 원소 기준으로 정렬됩니다.

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
pq.push({dist, node});           // 거리 작은 것이 먼저 나옴
auto [d, u] = pq.top(); pq.pop();

heapq.heappush(pq, (dist, node))
d, u = heapq.heappop(pq)         # 거리 기준 최소

다익스트라의 골격이 바로 이 형태입니다.

4. 응용: 실시간 중앙값 (두 힙)

값이 계속 들어올 때 중앙값을 \(O(\log N)\)에 유지합니다. 작은 절반은 최대 힙,
큰 절반은 최소 힙에 담고 크기를 균형 있게 맞춥니다.

import heapq
low = []    # 최대 힙(음수 저장): 작은 절반
high = []   # 최소 힙: 큰 절반

def add(x):
    heapq.heappush(low, -x)
    heapq.heappush(high, -heapq.heappop(low))   # low의 최대를 high로
    if len(high) > len(low):                    # 크기 균형
        heapq.heappush(low, -heapq.heappop(high))

def median():
    return -low[0]    # 홀수 개일 때 중앙값

5. 흔한 실수

• C++ 기본이 최대 힙 — 최소 힙을 원하면 greater<>. 헷갈리기 쉬움.
• 파이썬은 최소 힙뿐 — 최대 힙은 음수 트릭.
• 임의 삭제 기대 — 힙은 특정 값 삭제를 지원 안 함. "lazy deletion"
  (꺼낼 때 무효 원소 건너뛰기) 기법을 쓰세요.
• top/pop 전 비었는지 확인 — 빈 힙 접근은 에러.
• 튜플 비교 시 동률 — 첫 키가 같으면 다음 키로 비교되니, 비교 불가능한
  객체를 넣지 않도록 주의.

6. 패턴 알아보기

• "매번 최대/최소를 꺼내며 값이 들고 난다" → 우선순위 큐.
• "가장 가까운 정점부터" (가중치 그래프 최단 경로) → 다익스트라용 힙.
• "K개 중 가장 ~", "실시간 중앙값/상위 K" → 힙.

실전에서 우선순위 큐 문제 알아보기

힙이 필요한 문제는 한 가지 동작을 반복합니다 — "남은 것 중 가장 작은(큰)
것을 꺼내 처리하고, 새로 생긴 것을 넣는다." 이 루프를 알아보는 연습입니다.

1. 출제 신호

• "매번 가장 작은/큰 것을 골라" — 카드 합치기(작은 두 묶음을 반복해 합침),
  최소 비용 합병류.
• 삽입과 최솟값 추출이 뒤섞여 반복 — 정렬은 한 번뿐이라 못 쓰고, 매번
  정렬하면 \(O(N^2 \log N)\)이라 힙이 유일한 답인 구조.
• "절댓값이 가장 작은 수"처럼 비교 기준이 복합적 — (절댓값, 원래 값)
  튜플 키.
• \(k\)개의 정렬된 목록을 병합 — 각 목록의 머리만 힙에 유지.
• 시뮬레이션에서 "다음에 일어날 이벤트" — 시각이 가장 이른 이벤트를
  반복해 꺼내는 구조.

2. 풀이 결정 절차

1. 최소 힙인가 최대 힙인가 — 꺼내야 하는 것이 작은 쪽인지 큰 쪽인지.
2. 키를 설계합니다 — 단일 값이면 그대로, 동률 규칙이 있으면 튜플
   (1차 키, 2차 키)로.
3. 연산 횟수 × \(O(\log N)\) 이 제한 안인지 확인합니다.
4. 힙 안의 원소를 수정/삭제해야 하는가? — 힙은 임의 원소 접근이
   안 되므로, 필요하면 lazy deletion(꺼낼 때 무효 원소를 버림)을
   계획합니다.

3. 자주 하는 실수

• heapq로 최대 힙을 만들 때 부호 처리 절반만. 넣을 때 -x를 했으면
  꺼낸 값도 부호를 되돌려야 합니다.

import heapq
h = []
heapq.heappush(h, -x)        # 최대 힙: 음수로 넣고
top = -h[0]                  # 읽을 때도 부호 복원
largest = -heapq.heappop(h)  # 꺼낼 때도 복원

• C++ priority_queue 기본이 최대 힙임을 잊음. 최소 힙은
  priority_queue<int, vector<int>, greater<int>>. 출력이 정확히 거꾸로면
  십중팔구 이 실수입니다.
• 절댓값 힙에서 동률 규칙 누락. 절댓값이 같으면 "더 작은(음수) 값 먼저"
  같은 2차 규칙이 명시됩니다. 키를 (abs(x), x) 튜플로 만들면 한 번에
  해결됩니다.
• 오래된(무효) 원소를 그대로 신뢰. 값이 갱신되는 시뮬레이션에서는 꺼낸
  원소가 최신 상태와 일치하는지 확인하고, 아니면 버리고 다음을 꺼냅니다
  (lazy deletion). 갱신 시 힙 내부를 고치려 들지 마세요.
• 비교자 방향 혼동. C++ 커스텀 비교자에서 return a < b;는 최대 힙을
  만듭니다(정렬과 반대 느낌). 작은 예제로 꼭 확인하세요.

4. 연습 방법

이 페이지 오른쪽의 추천 문제는 쉬운 순 → 어려운 순입니다. 최소/최대 힙
기본 조작 → 절댓값 힙(튜플 키) → 반복 합치기·이벤트 시뮬레이션으로
이어집니다.

문제마다 "힙에 무엇을(키 설계), 언제 넣고 언제 꺼내는가"를 두 줄로
적고 시작하세요. 3문제 이상 풀어 클리어하면 레이팅의 CLASS 보너스에
반영됩니다.