19. c++ stl 우선순위 큐

● 우선순위 큐(priorith_queue) 컨테이너는 우선순위 queue를 구혀한 템플릿 클래스입니다. priority_queue 컨테이너에 설정된 기본 컨테이너는 vector입니다.

● priority_queue는 내부적으로 STL의 힙 알고리즘인 make_heap(), push_heap(), pop_heap()을 사용하여 구현돼 있으므로 priority_queue의 컨테이너 템플릿 인자로 받는 컨테이너는 임의 접근 반복자를 제공하는 컨테이너입니다. 또한, 이 컨테이너는 empty(), size(), push_back(), pop_back(), front() 등의 인터페이스를 제공해야 합니다.  그래서 priority_queue는 vector와 deque컨테이너는 사용할 수 있습니다

※ 다음 예제는 정수를 priority_queue 컨테이너에 저장하고 우선순위(내림차순, 오름차순 정렬)에 따라 출력하는 예제입니다

[ 우선순위 큐 예제1 ]

#include <iostream>
#include <queue>
using namespace std;
int main()
{
	priority_queue<int> pq1;  //기본 정렬기준 (내림차순)  
	
	pq1.push(40);
	pq1.push(20);
	pq1.push(30);
	pq1.push(50);
	pq1.push(10);
	
	cout << "priorith_queue[less] : " << '\n'; 
	while(!pq1.empty())
	{
		cout << pq1.top() << '\n';
		pq1.pop();
	}
	
	cout << "==============================" << '\n';
	
	priority_queue<int, vector<int>, greater<int> > pq2;  //오름차순 정렬 
	pq2.push(40);
	pq2.push(20);
	pq2.push(30);
	pq2.push(50);
	pq2.push(10);
	
	cout << "priority_queue[greater] : " << '\n'; 
	while(!pq2.empty())
	{
		cout << pq2.top() << '\n';
		pq2.pop();
	}
	 
	return 0;
}

※ pq1은 vector<int> 컨테이너를 사용하고 기본정렬 기준은 내림차순으로 출력하는 priority_queue 컨테이너입니다.

priority_queue<int> pq1;  //기본 정렬기준 내림차순

 

※ pq2는 vector<int> 컨테이너를 사용하고 오름차순 정렬 기준을 사용한 priority_queue 입니다. 

priority_queue<int, vector<int>, greater<int> > pq2;  //오름차순 정렬

※ 인터페이스는 stack과 비슷합니다.

 

[ 우선순위 큐 예제2 ]

※ 우선순위 큐에 pair를 사용하여 정수2개를 저장해서 사용해보는 예제입니다

#include <iostream>
#include <queue>
using namespace std;
typedef pair<int, int> ci;

struct compare
{
	bool operator() (ci a, ci b)
	{
		if(a.second > b.second) return 1;
		else return 0;
	}
};
int main()
{
	int a, b, i;
	ci t;
	priority_queue<ci> pq1;  //첫번째 항목으로 내림차순  

	pq1.push(make_pair(3,40));
	pq1.push(make_pair(5,20));
	pq1.push(make_pair(2,10));
	pq1.push(make_pair(4,50));
	pq1.push(make_pair(1,30));

	while(pq1.size())
	{
		t = pq1.top();
		cout << t.first << ' '<< t.second << '\n';
		pq1.pop();
	};
	
	cout << "========================" << '\n';
	
	priority_queue<ci, vector<ci>, greater<ci> > pq2; //첫번째 항목으로 오름차순   

	pq2.push(make_pair(3,40));
	pq2.push(make_pair(5,20));
	pq2.push(make_pair(2,10));
	pq2.push(make_pair(4,50));
	pq2.push(make_pair(1,30));

	while(pq2.size())
	{
		t = pq2.top();
		cout << t.first << ' '<< t.second << '\n';
		pq2.pop();
	};
	
	cout << "========================" << '\n';
	
	priority_queue<ci, vector<ci>, compare > pq3; //두번째 항목정렬    

	pq3.push(make_pair(3,40));
	pq3.push(make_pair(5,20));
	pq3.push(make_pair(2,10));
	pq3.push(make_pair(4,50));
	pq3.push(make_pair(1,30));

	while(pq3.size())
	{
		t = pq3.top();
		cout << t.first << ' '<< t.second << '\n';
		pq3.pop();
	};
	return 0;
}

※ pq1은 pair를 사용해서 2개를 저장해서 첫번째 항목기준으로 내림차순으로 출력하는 priority_queue 컨테이너입니다.

priority_queue<ci> pq1;  //첫번째 항목으로 내림차순

 

※ pq2은 pair를 사용해서 2개를 저장해서 첫번째 항목기준으로 오름차순으로 출력하는 priority_queue 컨테이너입니다.

priority_queue<ci, vector<ci>, greater<ci> > pq2; //첫번째 항목으로 오름차순

 

※ pq3은 pair를 사용해서 2개를 저장해서 두번째 항목기준으로 오름차순으로 출력하는 priority_queue 컨테이너입니다.

priority_queue<ci, vector<ci>, compare > pq3; //두번째 항목정렬