[C++] <queue> 라이브러리, 우선순위 큐, 최대 힙, 최소 힙

C++에서 우선순위 큐를 구현하려면 <queue> 라이브러리를 사용하면 된다. 따라서 #include <queue> 코드를 써줘야 한다.

priority_queue - C++ Reference

우선순위 큐를 선언하는 코드는 다음과 같다.

priority_queue<int, vector<int>> q;

이렇게 큐를 선언하면 숫자가 클 수록 우선순위가 높은 우선순위 큐가 만들어진다.

priority_queue<int, vector<int>> q;에서 이 안에서 int는 큐에 들어갈 데이터의 타입을 말한다.

priority_queue<int, vector<int>> q;에서 vector<int>는 데이터들이 들어갈 컨테이너이다. 실제로는 이 곳에 int 데이터들이 저장된다. 하지만 동작을 우선순위 큐 처럼 하게 하기 위해서 priorty_queue 타입으로 감싼 것이라고 보면 된다.

이렇게 선언하고 나서 우선순위 큐에 데이터를 집어넣으려면

q.push(3);

이렇게 push() 함수를 이용하면 된다.

 

q.push(4);
q.push(9);
q.push(1);
q.push(7);
q.push(10);
q.push(2);
q.push(3);

이렇게 7개의 int형 숫자 데이터를 우선순위 큐에 집어넣은 다음

 

while (!q.empty()) {
	cout << q.top() << endl;
	q.pop();
}

큐가 빌 때까지 pop 하면서 출력해보면 결과는 다음과 같다.

전체 코드는 아래와 같다.

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

int main() {
	priority_queue<int, vector<int>> q;
	q.push(4);
	q.push(9);
	q.push(1);
	q.push(7);
	q.push(10);
	q.push(2);
	q.push(3);
	while (!q.empty()) {
		cout << q.top() << endl;
		q.pop();
	}
	return 0;
}

 

우선순위 큐는 내부적으로 내림차순으로 정렬되어 있는 것을 볼 수 있다. 따라서 이렇게 pop 할 때마다 가장 큰 값을 반환한다. pop 할 때마다 가장 큰 값을 반환하는 것은 최대 힙(heap)의 성질과 같다.

따라서 priority_queue만으로 힙의 구현이 가능하다.

 

작은 데이터일수록 우선순위가 높은 우선순위 큐를 만들고 싶다면? 최소 힙을 만들고 싶다면?

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

<> 사이에 vector<int> 뒤에 콤마를 찍고 세 번째 인자(?)로 greater<int>를 넣어주면 된다.

greater라는 정렬 기준을 추가해준 것이다. greater는 오름차순 정렬이라는 소리이다.

최소힙인데 왜 오름차순이지? 할 수도 있는데 잘 생각해보면 큐는 front에서 원소를 빼는데 front는 인덱스가 0이므로 맨 앞에 가장 작은 값이 와야 한다. 따라서 오름차순으로 정렬해야

값이 작을 수록 우선순위가 높은 우선순위 큐 또는 최소힙을 만들 수 있다.

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

int main() {
	priority_queue<int, vector<int>, greater<int>> q;
	q.push(4);
	q.push(9);
	q.push(1);
	q.push(7);
	q.push(10);
	q.push(2);
	q.push(3);
	while (!q.empty()) {
		cout << q.top() << endl;
		q.pop();
	}
	return 0;
}

이 코드를 실행하면

이렇게 작은 값부터 나오는 것을 볼 수 있다.

 

최대힙을 만들 때에는 아까처럼 정렬 기준을 정해주지 않아도 디폴트가 내림차순 정렬이고

priority_queue<int, vector<int>, less<int>> q;

이렇게 정렬기준으로 less를 넣어줄 수도 있다. less는 내림차순으로 정렬하라는 것이다.