C++ STL::Queue::Priority_Queue

오늘은 Queue 헤더파일에 포함되어있는 우선순위 큐(Heap)에 대해서 포스팅합니다~

 

Heap은 Insertion과 Deletion에 최적화되어있는 자료구조입니다.

 

데이터를 특정 기준에 맞춰 정렬된 상태로 보관하기 때문에 복잡한 문제에서 이용하기 정말 좋아요.

 

★ 기본 우선순위 큐(내림차순) ★

아무것도 명시하지 않은 우선순위 큐는 내림차순으로 작동합니다!

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
priority_queue<int> pq;

int main() {
	pq.push(10000);
	pq.push(10);
	pq.push(100);
	pq.push(1000);
	pq.push(1);
	while (pq.empty() != true) {
		cout << pq.top() << endl;
		pq.pop();
	}
}

실행결과

★ 오름차순 우선순위 큐(greater) ★

 

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

 

맨 앞의 int는 큐의 원소가 될 자료형입니다.

두번째 vector<int>는 pq의 컨테이너 자료형입니다. 그러니까 원소가 담기는 그릇이라고 생각하시면 됩니다.

마지막 greater<int>는 우선순위 큐의 정렬 형태를 명시하는 코드입니다.

less<자료형>을 쓰게 되면 내림차순으로, greater<자료형>을 쓰게 되면 오름차순으로 정렬하게 됩니다.

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
priority_queue<int, vector<int>, greater<int>> pq;

int main() {
	pq.push(10000);
	pq.push(10);
	pq.push(100);
	pq.push(1000);
	pq.push(1);
	while (pq.empty() != true) {
		cout << pq.top() << endl;
		pq.pop();
	}
}

실행결과

★ 커스텀 비교 연산자 만들어 사용하기 ★

 

실제로 코딩을 할때 QUEUE에 원소가 1개짜리인 자료형을 넣는 경우는 드뭅니다 ㅎㅎ 

 

구조체나 2차원 배열을 넣기도 하고 아래 예제와 같이 2차원 벡터를 넣는 경우도 있거든요!

 

이때는 아래처럼 비교연산자를 포함한 구조체를 선언해주고, 그 구조체를 명시해줍니다.

 

비교연산자에는 어떤 원소를 기준으로 정렬할것인지를 명시해주면 됩니다!

 

return a[1] > b[1] 로 쓰면 오름차순 정렬이 되고, return a[1] < b[1]로 부호를 바꾸면 내림차순 정렬이 됩니다.

#include <iostream>
#include <vector>
#include <queue>

using namespace std;
struct cmp {
	bool operator()(vector<int> a, vector<int> b){
		return a[1] > b[1];
	}
};
priority_queue<vector<int>,vector<vector<int>>, cmp> pq;

int main() {
	vector<vector<int>> jobs = { {0, 3}, { 1, 9 }, { 2, 6 } };
	pq.push(jobs[0]);
	pq.push(jobs[1]);
	pq.push(jobs[2]);
	while (pq.empty() != true) {
		cout << pq.top()[0] << " " << pq.top()[1] << endl;
		pq.pop();
	}
}

실행결과

3-6-9 오름차순 정렬