priority_queue<T> 사용법

C++ priority_queue 정리. 핵심은 **기본이 최대 힙(Max-Heap)**이라는 점이다.

1) 기본 사용법 (최대 힙)

가장 큰 값이 top()에 온다.

#include <queue>
#include <iostream>

using namespace std;

int main() {
    // 기본: 큰 값 우선
    priority_queue<int> pq;

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

    cout << "Top element: " << pq.top() << endl; // 30

    pq.pop(); // 30 제거
    cout << "Next top: " << pq.top() << endl; // 20
}

2) 최소 힙 (Min-Heap)

가장 작은 값을 top()으로 두려면 세 번째 템플릿 인자로 greater<T>를 쓴다.

// priority_queue<자료형, 구현체, 비교연산자>
priority_queue<int, vector<int>, greater<int>> pq;

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

cout << pq.top() << endl; // 10

3) pair와 함께 사용하기

pair<int, int>는 기본 비교가 사전식(lexicographical)이다.

• 먼저 first를 비교
• first가 같으면 second를 비교

기본 priority_queue<pair<int, int>>에서는 큰 값이 우선이므로, first/second 모두 내림차순 우선순위를 가진다.

priority_queue<pair<int, int>> pq;

pq.push({5, 100}); // 거리 5, 인덱스 100
pq.push({5, 200}); // 거리 5, 인덱스 200
pq.push({10, 50}); // 거리 10, 인덱스 50

// 결과: {10, 50} -> {5, 200} -> {5, 100} 순으로 나옴

4) 핵심 멤버 함수

함수	설명	시간 복잡도
push(val)	요소 추가	$O(\log N)$
pop()	최우선 요소 제거	$O(\log N)$
top()	최우선 요소 조회 (제거 X)	$O(1)$
empty()	비어있는지 확인	$O(1)$
size()	요소 개수	$O(1)$

5) 커스텀 정렬 (구조체 comparator)

정렬 기준이 복잡하면 comparator를 직접 정의하는 것이 가장 안전하다.

예: 거리(first)는 큰 값 우선, 거리가 같으면 인덱스(second)는 작은 값 우선

struct Compare {
    bool operator()(pair<int, int> a, pair<int, int> b) {
        if (a.first == b.first) {
            return a.second > b.second; // 두 번째 인자는 작은 게 위로 (오름차순)
        }
        return a.first < b.first; // 첫 번째 인자는 큰 게 위로 (내림차순)
    }
};

priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;

주의: pop()은 반환값이 없다. 값을 사용하려면 top()을 먼저 읽고 pop()해야 한다.

6) greater<T> / less<T> 정리

greater<int>는 <functional>의 함수 객체다. 내부적으로 a > b 비교를 수행한다.

template <typename T>
struct greater {
    bool operator()(const T& a, const T& b) const {
        return a > b;
    }
};

사용 예시

• sort(..., greater<int>()) -> 내림차순 정렬
• priority_queue<int, vector<int>, greater<int>> -> 최소 힙

vector<int> v = {1, 4, 2, 5, 3};
sort(v.begin(), v.end(), greater<int>()); 
// 결과: {5, 4, 3, 2, 1}

priority_queue<int, vector<int>, greater<int>> pq;

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

cout << pq.top() << endl; // 10

less vs greater 비교

기능	less<T> (기본값)	greater<T>
비교 연산	a < b	a > b
std::sort 결과	오름차순	내림차순
priority_queue 결과	최대 힙	최소 힙

7) C++14 이후 간결한 표기

C++14부터는 greater<int>() 대신 greater<>()를 쓸 수 있다.

sort(v.begin(), v.end(), greater<>());

정리: 코테에서 우선순위 큐는 "기본 최대 힙"을 먼저 기억하고, 최소 힙이 필요하면 greater<T>를 넣는 습관을 들이면 실수를 크게 줄일 수 있다.