[C++] STL Priority_Queue Library 기본 명령어 정리

안녕하세요, 여행벌입니다.

오늘은 우선순위큐(Priority Queue)에 대해서 알아보도록 하겠습니다.

---

1. Priority_Queue(우선순위큐) 란?

Priority_Queue는 Queue의 한 종류로 이름 그대로 우선순위에 따라 정렬된 Queue입니다.

[Queue 포스팅 : https://travelbeeee.tistory.com/7?category=807507 ]

어떤 원소가 Push(삽입)된다면 주어진 우선순위에 맞춰서 Queue가 정렬되고, Pop(삭제)는 정렬된 Queue의 앞에서 이루어집니다. 자료구조 Heap으로 구현되었기 때문에, 특정 원소를 Push해 생기는 정렬 과정은 O(logN) 만에 이루어집니다.

 

2. C++ STL 우선순위큐 라이브러리 기본 명령어

#include<queue>

queue와 동일한 Library에서 지원해줍니다.

선언
- priority_queue<자료형, Container, 비교함수> 변수명
선언한 자료형 변수들을 비교함수에 따라 정렬하는 Priority_Queue(우선순위큐)를 선언.

- priority_queue<자료형> 변수명
선언한 자료형 변수들을 내림차순에 따라 정렬하는 Priority_Queue(우선순위큐)를 선언.

ex) priority_queue<int, vector<int>, cmp> pq 
int형 변수들을 cmp 우선순위에 따라 정렬하는 pq라는 이름의 Priority_queue(우선순위큐)를 선언.

추가 및 삭제
- push(element) : Priority_Queue(우선순위큐)에 원소를 삽입. ( 비교함수에 따라 내부적으로 정렬됨 )
- pop() : 맨 앞에 있는 원소를 삭제.

서칭
- top() : 맨 앞에 있는 원소를 반환.

기타
- empty() : Priority_Queue(우선순위큐)가 비어있으면 true 아니면 false를 반환
- size() : Priority_Queue(우선순위큐)의 크기를 반환

기본 함수는 다음과 같습니다.

 

이제, 예시를 통해서 익혀보겠습니다.

[예시1) 기본 - 내림차순]

#include<iostream>
#include<queue>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	priority_queue<int> pq;
	pq.push(5);
	pq.push(1);
	pq.push(7);
	for (int i = 0; i < 3; i++){
		cout << pq.top() << ' ';
		pq.pop();
	}
}

출력
7 5 1

int형 원소들을 내림차순에 따라 정렬하는 우선순위큐를 만들었습니다.

5 / 1 / 7 을 차례대로 입력하고 하나하나 출력해보니 7 / 5 / 1 순으로

비교기준(내림차순)에 따라 정렬되어있는 것을 확인할 수 있습니다.

#include<iostream>
#include<queue>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	priority_queue<char> pq;
	pq.push('5');
	pq.push('1');
	pq.push('7');
	for (int i = 0; i < 3; i++){
		cout << pq.top() << ' ';
		pq.pop();
	}
}

출력
7 5 1

이번에 char형 원소들을 내림차순에 따라 정렬하는 우선순위큐를 만들었습니다.

마찬가지로, 아스키코드값이 더 큰 '7', '5', '1' 순으로 정렬되어있는 것을 볼 수 있습니다.

 

[예시2) 기본 - 올림차순]

#include<iostream>
#include<queue>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	priority_queue<int, vector<int>, greater<int>> pq;
	pq.push(5);
	pq.push(1);
	pq.push(7);
	for (int i = 0; i < 3; i++){
		cout << pq.top() << ' ';
		pq.pop();
	}
}

출력
1 5 7

비교함수에 greater<int> 를 넣어주면 반대로 오름차순에 따라 정렬되는 우선순위큐를 만들 수 있습니다.

#include<iostream>
#include<queue>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	priority_queue<char, vector<char>, greater<char>> pq;
	pq.push('5');
	pq.push('1');
	pq.push('7');
	for (int i = 0; i < 3; i++){
		cout << pq.top() << ' ';
		pq.pop();
	}
}

출력
1 5 7

char형 변수에서도 greater<char>를 넣어주면 오름차순에 따라 정렬되는 우선순위큐를 만들 수 있습니다.

 

[예시3) 비교함수 선언1]

내림차순, 오름차순으로 정렬하는 우선순위큐는 쉽게 선언할 수 있습니다.

그렇다면, 내가 원하는 우선순위를 지정해주려면 어떻게 해야 될까요?

연산자 오버로딩을 통해 원하는 우선순위대로 구현할 수 있습니다.

아래 예시를 통해서 익혀보겠습니다.

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

struct cmp {
	bool operator()(int n1, int n2) {
		if (abs(n1) > abs(n2))
			return true;
		else if (abs(n1) == abs(n2))
			if (n1 > n2)
				return true;
			else
				return false;
		return false;
	}
};

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	priority_queue<int, vector<int>, cmp> pq;
	pq.push(1);
	pq.push(-1);
	pq.push(7);
	pq.push(-4);
	pq.push(15);

	for (int i = 0; i < 5; i++){
		cout << pq.top() << ' ';
		pq.pop();
	}
}

먼저 struct cmp 부분을 살펴보겠습니다.

struct cmp {
	bool operator()(int n1, int n2) {
		if (abs(n1) > abs(n2))
			return true;
		else if (abs(n1) == abs(n2))
			if (n1 > n2)
				return true;
			else
				return false;
		return false;
	}
};

위의 코드는 '절대값이 더 작은 값에 우선순위를 높게 주고, 절대값이 같다면 더 작은 값에 우선순위를 높게 줄 거예요!' 

라고 선언한 것과 같습니다.

따라서, 다음과 같이 출력됩니다.

출력
-1 1 -4 7 15

---

우선순위큐 포스팅은 여기서 마치겠습니다.