[C++, STL] 우선순위 큐(priority queue) 비교연산자 구현

by

사용자 정의 우선순위 큐

[C++, STL] 알고리즘 문제풀이를 위한 우선순위 큐(priority queue)

우선순위 큐는 비교연산자를 통해 자료의 우선순위를 정할 수 있다. 그리고 STL에는 자료를 오름차순, 내림차순으로 정렬해주는 greater, less가 미리 구현되어 있어서 편리하게 이용할 수 있다. 그러나 greater, less가 만족스럽지 않다면 사용자가 직접 비교연산자를 구현할 수 있다.

우선순위 큐 선언

우선순위 큐를 사용하기 위해서 queue 헤더파일을 가져온다. 네임스페이스는 std이다.

#include <queue>
using namespace std;
int main(){
	priority_queue<int, vector<int>, compare>pq; // 자료형 int, 컨테이너 vector, 사용자 정의 비교연산자 compare
}

비교연산자 구현

정수를 오름차순으로 정렬하는 비교연산자 구현

struct compare{
    bool operator()(int a, int b){
        return a>b;
    }
};

우선순위 큐 내부에 새로운 자료가 들어가면 자신의 부모 노드와 크기를 비교하고 비교연산자 조건에 따라 swap 하게 된다. 이 행위는 더 이상 swap이 일어나지 않을 때까지 반복한다.

위 코드에서 a는 부모 노드이고 b는 현재 노드다. 만약 a가 b보다 크다면 true를 리턴해서 swap을 진행한다. 이를 반복하다 보면 조상 노드는 가장 작은 원소가 차지할 것이다.

struct compare{
    bool operator()(int a, int b){
        return a<b; // 오름차순과 유일하게 다른 라인
    }
};

위 코드는 반대로 a가 b보다 크다면 false를 리턴하고 swap를 진행하지 않아서 조상 노드는 가장 큰 원소가 차지하게 된다. compare를 구현하기 위한 핵심은, 두 자료를 비교했을 때 swap를 해줄 것인지 말 것인지 결정하는 것이다.

비교연산자 응용

pair의 second를 기준으로 오름차순 정렬

struct compare{
	bool operator()(pair<int, int>a, pair<int, int>b){
		return a.second>b.second;
	}
};

int main(){
	priority_queue<pair<int, int>, vector<pair<int, int>>, compare>pq;
	pq.push({1, 10});
	pq.push({2, 3});
	pq.push({3, 1});
	cout<<pq.top().first; // 출력 : 3
	cout<<pq.top().second; // 출력 : 1
}

우선순위 큐에 자료형으로 pair, struct를 사용하면 하나의 원소에 여러 자료가 들어갈 수 있다. 위 코드에서는 pair로 하나의 원소에 두 개의 자료를 넣었다.

-> ( {1, 10}, {2, 3}, {3, 1} )

그리고 compare에서 각 원소의 second값을 기준으로 오름차순 정렬했다.

-> ( {3, 1}, {2, 3}, {1, 10} )

실제로 조상 노드를 제외하고 완벽하게 정렬되지는 않는다.

만약 compare를 따로 구현하지 않았다면 first를 기준으로 정렬했을 것이다. 이렇게 하면 first를 실제 자료로, second를 가중치로 지정할 수 있다.

Leave a Comment