<priority_queue> 자료구조

 Priority_Queue는 Queue 의 한 종류인데 말 그대로 우선순위에 따라 정렬된 Queue라고 보면 도니다. <queue> 와 동일한 라이브러리에서 지원 해주며 특정 원소를 push 를 할 때 O(logN)만에 이루어진다. 해당 시간 복잡도가 이해가 안간다면 자료구조 [힙] 이라는 것을 search 해보길 바란다. Priority_Queue 는 힙 구조로 되어있다.

 

priority_queue<자료형> 변수명 : 생성

priority_queue<int, vector<int, cmp> 변수명 : cmp 우선순위에 따라 정렬

push(값) : 우선순위큐에 우선순위에 따라 원소를 삽입

pop(값) : 맨앞에 있는 원소 삭제

top() : 맨앞에 있는 값 반환

empty() : 비어있으면 1로 반환 아니라면 0 반환

size() : 큐의 사이즈값 반환

 

priority_queue 는 내림차순으로 기본적으로 정렬되어있따. 그렇기 때문에 queue를 pop 한다면 

제일 큰 값이 pop 된단 오름차순으로 정렬 하기 위해서는 

처음 queue를 생성을 할 때 비교함수에 greater<int>를 추가적으로 넣어준다면 내림차순으로 

정렬된다. 

 

사용자 정의에 의해서 정렬 될 수도 있는데 cmp라는 구조체에서 bool 연산자를 통해 파라미터로 받아온 값을 비교해 어떻게 리턴할지 작성하면 사용자 정의에 따라 정렬 될 수 있다. 

 

다음 코드를 보고 어떻게 정렬되는지 출력 해보고 익숙해질때까지 연습하고 외우도록 하자. 

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

using namespace std; 

struct cmp {
	bool operator()(int n1, int n2) {
		return n1>n2;
	}
};


int main() {
	priority_queue<int> q; 
	q.push(1); 
	q.push(3); 
	q.push(2); 
	for (int i = 0; i < 3; i++) {
		cout << q.top() << " ";
		q.pop();
	}cout << "\n"; 
	priority_queue<int, vector<int>, greater<int>> q2;
	q2.push(1);
	q2.push(3);
	q2.push(2);
	for (int i = 0; i < 3; i++) {
		cout << q2.top() << " ";
		q2.pop();
	}cout << "\n"; 
	priority_queue<int, vector<int>, cmp>q3; 
	q3.push(1);
	q3.push(3);
	q3.push(2);
	for (int i = 0; i < 3; i++) {
		cout << q3.top() << " ";
		q3.pop();
	}
}

 

struct cmp {   
          bool operator()(pair<int, int>&a, pair<int, int>&b) {
              if (a.first == b.first) return a.second < b.second;              
              else return a.first > b.first;              
          }
      };
	priority_queue<pair<int,int>,vector<pair<int,int>>, cmp> pq;
	pq.push({ 5,4 });
	pq.push({ 2,2 });
	pq.push({ 1,1 });

	while (!pq.empty())
	{
		cout << pq.top().first << pq.top().second << '\n';
		pq.pop();
	}

* 위와 같이 pair 된 queue도 활용 할 수 있으니 출력해보길 바란다. 

 

 

 

#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();
	}
}

출력 

0 3

2 6

1 9