[C++] 우선순위 큐: `priority_queue<T, Container, Compare>`

C++에서 “우선순위 큐(priority queue)”는 힙(heap) 자료구조를 아주 쉽게 사용할 수 있도록 만든 컨테이너입니다.

보통 queue<int>처럼 단순한 순서(FIFO)가 아니라,

“값의 크기나, 내가 정한 기준(priority)”에 따라 가장 우선순위가 높은 요소가 먼저 나오는 구조

를 제공합니다.

---

1. priority_queue란?

priority_queue는 내부적으로 힙(Heap) 구조를 이용하는 컨테이너 어댑터(Container Adapter) 입니다.

• 데이터를 담는 컨테이너(vector)
• 그 데이터를 정렬할 기준(Compare)
• 그리고 그걸 조합한 인터페이스(priority_queue)로 구성되어 있습니다.
  

정의는 다음과 같습니다 👇

template <
    class T,                          // 원소 타입
    class Container = vector<T>,      // 내부 컨테이너
    class Compare = less<typename Container::value_type> // 비교 기준
> class priority_queue;

즉,

priority_queue<T, Container, Compare>

으로 구성되어 있습니다.

---

2. 기본 사용법

C++의 priority_queue는 기본적으로 “큰 값이 먼저 나오는 최대 힙(Max-Heap)” 입니다.

#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int> pq;

    pq.push(10);
    pq.push(5);
    pq.push(30);

    cout << pq.top() << '\n'; // 30 (가장 큰 값)
}

출력 결과:

30

---

3. 내부 동작 방식

priority_queue는 내부적으로 완전 이진 트리 형태의 힙을 vector에 저장합니다.
push() 시에는 삽입된 값이 힙 구조를 유지하도록 O(logN) 시간 내에 자리잡고,
pop() 시에도 최상단(가장 우선순위 높은 값)을 제거한 뒤 구조를 재정렬합니다.

연산	시간 복잡도	설명
push()	O(log N)	새 원소 추가
pop()	O(log N)	top 제거 후 힙 재정렬
top()	O(1)	우선순위 가장 높은 값 조회

---

4. 최소 힙(Min-Heap) 만들기

기본은 최대 힙이지만,
다익스트라나 절댓값 힙처럼 작은 값이 먼저 나와야 하는 경우가 많습니다.
그럴 땐 비교자를 바꿔주면 됩니다 👇

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    priority_queue<int, vector<int>, greater<int>> minHeap;

    minHeap.push(10);
    minHeap.push(5);
    minHeap.push(30);

    cout << minHeap.top() << '\n'; // 5 (가장 작은 값)
}

✅ 핵심 포인트

greater는 “a > b일 때 true”를 반환하는 비교자입니다.

즉, 큰 값은 뒤로 밀리고 작은 값이 top에 오는 ‘최소 힙’이 됩니다.

비교자	top()에 남는 값	힙 종류
less<int> (기본)	가장 큰 값	최대 힙
greater<int>	가장 작은 값	최소 힙

---

5. 세 가지 인자 구조 완전 해부

priority_queue<T, Container, Compare>

인자	의미	기본값
T	저장할 데이터 타입	—
Container	내부 저장 컨테이너 (보통 vector)	vector<T>
Compare	우선순위 비교 기준	less<T> (큰 값 우선)

예시로 보면

priority_queue<int> pq;
// == priority_queue<int, vector<int>, less<int>>

less<int>는 “a < b”일 때 b가 우선순위가 높음 → 큰 값이 top (최대 힙)

priority_queue<int, vector<int>, greater<int>> pq;
// 작은 값이 top (최소 힙)

---

6. pair를 사용한 복합 우선순위

예를 들어,
절댓값이 작은 수가 먼저 나오고,
절댓값이 같으면 실제 값이 작은 수가 먼저 나오게 하려면 어떻게 할까?

👉 바로 pair와 greater를 함께 사용하면 됩니다.

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;

int main() {
    priority_queue<pair<long long,int>,
                   vector<pair<long long,int>>,
                   greater<pair<long long,int>>> pq;

    pq.push({ llabs(-3), -3 });
    pq.push({ llabs(3), 3 });
    pq.push({ llabs(-2), -2 });
    pq.push({ llabs(5), 5 });

    while (!pq.empty()) {
        cout << pq.top().second << ' '; // 실제 값 출력
        pq.pop();
    }
}

출력:

-2 -3 3 5

핵심 개념: pair는 두 값을 “사전식으로(lexicographical)” 비교한다

C++에서 pair는 두 개의 값을 묶어서 다루는 자료형입니다.
예를 들어 (abs(x), x) 형태로 저장하면,
첫 번째 값(first) 과 두 번째 값(second) 를 차례로 비교합니다.

따라서,
1️⃣ 먼저 first(절댓값)를 비교
2️⃣ 같다면 second(실제 값)를 비교

👉 이를 “사전식 비교”라고 부릅니다.

사전에서 단어를 정렬할 때,
앞 글자가 다르면 앞 글자 기준으로 정렬하고,
같으면 다음 글자를 비교하는 방식과 같습니다.

greater<pair<long long,int>>가 하는 일

greater는 “a > b일 때 true”를 반환하는 비교자입니다.
즉, 작은 값이 top으로 오게 만드는 “오름차순 기준"

pair와 결합되면 이렇게 작동합니다 👇

비교 순서	설명
1️⃣ 절댓값(first)이 작은 순	작은 절댓값이 우선
2️⃣ 절댓값이 같다면 실제값(second)이 작은 순	음수 → 양수 순으로

동작 과정 예시

우리가 넣은 값들을 (abs(x), x)로 보면:

(3, -3)
(3, 3)
(2, -2)
(5, 5)

이제 pair는 (first → second) 순으로 정렬합니다.

비교 대상	비교 기준	결과
(2, -2) vs (3, -3)	2 < 3 → ✅	(2, -2) 우선
(3, -3) vs (3, 3)	first 같음 → -3 < 3 → ✅	(3, -3) 우선

➡️ 최종 정렬 순서

(2, -2) → (3, -3) → (3, 3) → (5, 5)

따라서 실제 출력은

-2 -3 3 5

---

7. 자주 활용하는 예시 & 언제 써야 할까?

활용 예시

상황	구성 예시	설명
최소 힙	priority_queue<int, vector<int>, greater<int>>	작은 값부터
최대 힙	priority_queue<int>	큰 값부터
절댓값 기준	priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>>	절댓값 작은 순
다익스트라(가중치 작은 순)	priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>>	거리 기준 오름차순
사용자 정의 정렬	priority_queue<T, vector<T>, Compare>	자유로운 조건

다음과 같은 문제 상황에 사용

알고리즘	역할	우선순위 기준
다익스트라	가장 짧은 거리 노드 우선	거리
A* 탐색	f = g+h가 가장 작은 노드 우선	f값
K번째 큰 수	상위 K개 원소 유지	최소 힙
절댓값 힙	절댓값 작은 수 우선
스케줄링	우선순위 높은 작업 먼저	커스텀 기준

---

💬 마무리 요약

항목	요약
구조	priority_queue<T, vector<T>, Compare>
기본	최대 힙 (큰 값이 먼저)
최소 힙	greater<T>
복합 기준	(key1, key2) → pair
직접 비교	struct Compare
복잡도	push/pop: O(logN)
헤더	<queue>, <vector>, <functional>
응용	다익스트라, 힙정렬, 절댓값 힙, 스케줄러