[C++/Algorithm] priority_queue 사용법

Queue라는 자료구조는 선입 선출, 즉 먼저 들어온 data가 먼저 나가는 구조로 되어있다.

 

PriorityQueue라는 자료구조는 이 Queue라는 자료구조의 입 출력 순서를 지키면서, Queue에 내장되어 있는 data는 자동적으로 정렬이 되어있게끔 만들어 주는 자료구조이다.

 

즉 선입선출 + 자동정렬이라고 간단하게 생각하면 된다.

 

이 PriorityQueue를 C++ stl library로 사용하려면 

 

#include <bits/stdc++.h>
#include <queue>

 위의 라이브러리를 포함하거나, queue library를 포함해주면 사용할 수 있다.

 

기본적인 선언부는 다음과 같다.

// priority_queue<자료형, 구현체, 비교연산자>

 

다음과 같은 간단한 코드로 예시를 들어보겠다.

#include <bits/stdc++.h>
using namespace std;

int main(){
	ios::sync_with_stdio(false);
	
	priority_queue<int, vector<int>, greater<int>> pq;
	// priority_queue<자료형, 구현체, 비교연산자>
	// 오름차순 
	
	// priority_queue<int, vector<int>, less<int>> pq;
	// 내림차순
	
	for (int i = 10; i >= 0; i--) {
		pq.push(i);
	} 
	
	while(!pq.empty()) {
		cout << pq.top() << " ";
		pq.pop();
	}
    // result: 0 1 2 3 4 5 6 7 8 9 10
}

 

 

비교 연산자에 greater <int>를 넣어주게 되면 오름차순으로 자동 정렬이 이루어진다.

10~0까지 push를 하고 순서대로 출력을 해 준 결과 0~10이 출력된 것을 확인할 수 있다.

 

보통 위와 같이 작은 수부터 큰 수 까지 정렬되어 있는 queue를 Min Heap이라 하며, 그 반대를 Max Heap이라 한다.

 

한 가지만 더 짚고 넘어가자.

 

#include <bits/stdc++.h>
using namespace std;

int main(){
	ios::sync_with_stdio(false);
	
	// priority_queue<int, vector<int>, greater<int>> pq;
	// priority_queue<자료형, 구현체, 비교연산자>
	// 오름차순 
	
	// priority_queue<int, vector<int>, less<int>> pq;
	// 내림차순
	
	priority_queue<int> pq;
	
	for (int i = 10; i >= 0; i--) {
		pq.push(i);
	} 
	
	while(!pq.empty()) {
		cout << pq.top() << " ";
		pq.pop();
	}
    // result = 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0
}

구현체, 비교 연산자를 생략하고, 위와 같이 자료형만 명시하여도 코드는 정상적으로 작동한다. 이 경우 가장 큰 10부터 0까지 순서대로 출력되게 되는데 위의 예시로 c++ stl에서 제공하는 priority queue는 기본적으로 Max Heap(내림차순)으로 설정되어 있는 것을 확인할 수 있다.

 

* int, long, float... 등 기본 자료형 말고 Customizing 한 데이터로 구현하고 싶은 경우

위의 예시는 int형 즉 기본적인 자료형을 예시로 만든 가장 간단한 코드이고, 우리가 실제로 코드를 작성하다 보면 문제에 따라서 Custom 한 구조체의 자료형이 들어가는 경우도 있다.

 

가령

struct Edge {
	int start_node;
	int end_node;
	int weight;
};

위와 같이 간단하게 구조체를 정의하여 문제를 풀 수도 있다.

 

위의 Edge라는 structure로 Priority Queue를 사용하고 싶으면 다음과 같이 정의하면 된다.

#include <bits/stdc++.h>
using namespace std;

struct Edge {
	int start_node;
	int end_node;
	int weight;
	Edge (int w) : start_node(0), end_node(0), weight(w) { }
	
};

bool operator < (Edge e1, Edge e2) {
	return e1.weight < e2.weight;
}


int main(){
	ios::sync_with_stdio(false);
	
	priority_queue<Edge> pq;
	
	for (int i = 0; i <= 10; i++) {
		pq.push(Edge(i));
	} 
	
	while(!pq.empty()) {
		cout << pq.top().start_node << " " << pq.top().end_node << " " << pq.top().weight << endl;
		pq.pop();
	}
	/*
		result
		0 0 10
		0 0 9
		0 0 8
		0 0 7
		0 0 6
		0 0 5
		0 0 4
		0 0 3
		0 0 2
		0 0 1
		0 0 0
	*/
}

정렬을 weight 기준으로 할 것이기 때문에 일단 임시적으로 priority queue의 작동을 확인하기 위해서 생성자에 따로 node번호를 받지 않고 0을 default 값으로 주었다.

 

기본적으로 operator < 를 오버로딩 하여 Edge structure끼리 < 연산자로 비교 가능하게 만들었다. 위와 같이 간단하게 연산자 오버 로딩을 활용하여 Edge에 비교가 가능하게 만들어 주면 priority queue에서도 해당 연산자로 크기 비교를 하여 정렬한 결과를 저장하여 준다.

 

혹은 구조체로 비교연산자를 정의할 수도 있는데, 

#include <bits/stdc++.h>
using namespace std;

struct Edge {
	int start_node;
	int end_node;
	int weight;
	Edge (int w) : start_node(0), end_node(0), weight(w) { }
	
};

/*
struct compare{
	bool operator < (Edge e1, Edge e2) {
		return e1.weight < e2.weight;
	}
};
error...
*/

struct compare{
	bool operator () (Edge e1, Edge e2) const {
		return e1.weight < e2.weight;
	}
};
	
bool operator < (Edge e1, Edge e2) {
	return e1.weight < e2.weight;
}


int main(){
	ios::sync_with_stdio(false);
	
	priority_queue<Edge, vector<Edge>, compare> pq;
	
	for (int i = 0; i <= 10; i++) {
		pq.push(Edge(i));
	} 
	
	while(!pq.empty()) {
		cout << pq.top().start_node << " " << pq.top().end_node << " " << pq.top().weight << endl;
		pq.pop();
	}
	/*
		result
		0 0 10
		0 0 9
		0 0 8
		0 0 7
		0 0 6
		0 0 5
		0 0 4
		0 0 3
		0 0 2
		0 0 1
		0 0 0
	*/
}

위와 같이 비교연산자를 직접 구조체로 정의할 경우 operator <만 오버 로딩하게 되면 에러가 난다. 

위와 같이 operator ()를 오버로딩 하여 사용해야 한다.

 

아마 컴파일 과정에서 나머지 연산자에 대한 정의가 오버 로딩되지 않아서 에러가 나는 것 같다.

 

*저의 글에 대한 피드백이나 지적은 언제나 환영합니다.