C++에서 pair 우선순위 큐 구현하기 – 첫 번째 요소 기준 정렬

우선순위 큐(Priority Queue)는 우선순위가 부여된 요소들의 집합을 저장하는 추상 자료형(ADT)으로, 각 요소의 우선순위에 따라 삽입과 삭제를 지원합니다. 즉, 가장 높은 우선순위를 가진 요소는 언제든지 먼저 제거될 수 있습니다. 스택(Stack), 큐(Queue), 리스트(List)처럼 위치에 따라 선형적으로 요소를 저장하는 자료구조와 달리, 우선순위 큐는 요소들을 우선순위를 기준으로 저장한다는 점이 특징입니다.

우선순위 큐가 지원하는 주요 연산은 다음과 같습니다.

size() – 우선순위 큐에 포함된 요소의 개수를 반환하여 크기를 계산합니다.
empty() – 우선순위 큐가 비어 있으면 true, 그렇지 않으면 false를 반환합니다.
insert(element) – 새로운 요소를 우선순위 큐에 삽입합니다.
min() / top() – 가장 작은 키 값과 연관된 요소를 반환하며, 큐가 비어 있으면 오류 메시지를 출력합니다.
removeMin() / pop() – min() 함수가 참조하는 요소를 제거합니다.

이번 글에서 다룰 과제는 C++에서 pair(쌍)를 저장하되 첫 번째(first) 요소를 기준으로 정렬되는 우선순위 큐를 구현하는 것입니다.

힙(heap)과 유사한 방식으로 이 문제를 해결할 수 있으며, 두 가지 접근 방법이 있습니다.

최대 우선순위(Max Heap, 최대 힙)
최소 우선순위(Min Heap, 최소 힙)

힙은 노드들이 특정한 순서로 배치된 트리 구조입니다. 힙에는 최소 힙과 최대 힙 두 종류가 있는데, 최소 힙에서는 루트 노드(부모 노드)가 자식 노드보다 작고, 최대 힙에서는 루트 노드(부모 노드)가 자식 노드보다 큽니다. 참고로 C++ STL의 pair는 기본적으로 first 값을 먼저 비교하고, first 값이 같으면 second 값을 비교합니다.

예시 입력 및 출력

입력: priorityq.push(make_pair(18, 200))
priorityq.push(make_pair(29, 100))
priorityq.push(make_pair(11, 400))
출력: 29 100

입력: priorityq.push(make_pair(10, 200))
priorityq.push(make_pair(20, 100))
priorityq.push(make_pair(19, 400))
출력: 20 100
→ 최대 우선순위(Max Heap) 방식

알고리즘 (최대 힙)

Start
Step 1-> main 함수 내부에서
    priority_queue<pair<int, int> > priorityq 정의
    priorityq.push(make_pair(18, 200)) 호출
    priorityq.push(make_pair(29, 100)) 호출
    priorityq.push(make_pair(11, 400)) 호출
    pair<int, int> top = priorityq.top() 설정
    top.first와 top.second 출력
Stop

예제 코드 (최대 힙)

#include <bits/stdc++.h>
using namespace std;
// 메인 프로그램
int main() {
    priority_queue<pair<int, int> > priorityq;
    priorityq.push(make_pair(18, 200));
    priorityq.push(make_pair(29, 100));
    priorityq.push(make_pair(11, 400));
    pair<int, int> top = priorityq.top();
    cout << top.first << " " << top.second;
    return 0;
}

출력 결과

29 100

C++의 기본 priority_queue는 최대 힙으로 동작하며, pair를 저장할 경우 first 값을 기준으로 내림차순 정렬됩니다. 따라서 first 값이 가장 큰 (29, 100)이 top에 위치하게 됩니다.

최소 힙(Min Heap) 방식

반대로 first 값이 가장 작은 pair를 얻으려면 greater 비교자(comparator)를 사용해야 합니다.

알고리즘 (최소 힙)

Start
Step 1-> main 함수 내부에서
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> pq 정의
    pq.push(make_pair(10, 200)) 호출
    pq.push(make_pair(20, 100)) 호출
    pq.push(make_pair(15, 400)) 호출
    pair<int, int> top = pq.top() 설정
    top.first와 top.second 출력
Stop

예제 코드 (최소 힙)

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
// 메인 프로그램
int main() {
    priority_queue<pi, vector<pi>, greater<pi> > pq;
    pq.push(make_pair(10, 200));
    pq.push(make_pair(20, 100));
    pq.push(make_pair(15, 400));
    pair<int, int> top = pq.top();
    cout << top.first << " " << top.second;
    return 0;
}

출력 결과

10 200

greater<pi> 비교자를 사용하면 pair의 first 값을 기준으로 오름차순 정렬되므로, first 값이 가장 작은 (10, 200)이 top에 위치합니다. 만약 first 값이 서로 같다면 second 값을 기준으로 비교가 진행된다는 점도 기억해 두면 좋습니다.