[C++] [STL] 8. priority_queue

priority_queue 주요 함수

<기본형태>

• priority_queue<T, Container, Compare> : 원하는 자료형 및 클래스 T를 통해 생성. 여기서 Container는 vector와 같은 컨데이터이며 Compare는 비교함수 클래스이다. 

<추가 및 삭제>

• insert(element) : 우선순위 큐에 원소 추가 
• pop() : 우선순위 큐에서 top의 원소를 삭제

<조회>

• top() : top에 있는 원소를 반환

<기타>

• empty() : 리스트가 비어있음 true 아님 false반환 
• size() : 리스트 원소들의 갯수를 반환

 

 

예제 코드

Max Heap 구현

#include<queue>	//그냥 queue 인클루드하면됨~

int main(void) {
	//priority_queue
	priority_queue<int, vector<int>, less<int>> pq;	//less 써서 내림차순정렬
	//priority_queue<int> pq;	//이것도 가능

	//push(element)
	// 5 2 8 9 1 14 --> less 때문에 14 9 8 5 2 1
	pq.push(5);
	pq.push(2);
	pq.push(8);
	pq.push(9);
	pq.push(1);
	pq.push(14);

	//pop()
	// 8 5 2 1
	pq.pop();
	pq.pop();

	//top()
	// 8
	cout << "pq top : " << pq.top() << endl;

	//empty(), size()
	if (!pq.empty())
		cout << "pq size : " << pq.size() << endl;

	//pop all
	while (!pq.empty()) {
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;
}

 

Min Heap 구현

#include<queue>		//그냥 queue 인클루드하면됨~
#include<functional>	//greater<int> 사용 시 필요

int main(void) {
	//priority queue
	priority_queue<int, vector<int>, greater<int>> pq; //greater 써서 오름차순정렬

	//push(element)
	// 5 2 8 9 1 14 --> greater 때문에 1 2 5 8 9 14
	pq.push(5);
	pq.push(2);
	pq.push(8);
	pq.push(9);
	pq.push(1);
	pq.push(14);

	//pop()
	// 5 8 9 14
	pq.pop();
	pq.pop();

	//top()
	cout << "pq top : " << pq.top() << endl;

	//empty(), size()
	if (!pq.empty())
		cout << "pq size : " << pq.size() << endl;

	//pop all
	while(!pq.empty()) {
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;
}

 

구조체, 비교함수 이용

#include<queue>	//그냥 queue 인클루드하면됨~

struct Custom {
	int x;
	int y;
	int value;
	Custom(int value) :x(0), y(0), value(value) {
	}
};
//오름차순 정렬***
struct cmp {
	bool operator()(Custom t, Custom u) {
		return t.value > u.value;
	}
};

int main(void) {
	//priority_queue
	priority_queue<Custom, vector<Custom>, cmp> pq;	//구조체라 less<Custom> 이건 안먹는듯

	//push(element)
	//
	pq.push(Custom(5));
	pq.push(Custom(2));
	pq.push(Custom(8));
	pq.push(Custom(9));
	pq.push(Custom(1));
	pq.push(Custom(14));

	//pop()
	pq.pop();
	pq.pop();

	//top()
	cout << "pq top : " << pq.top().value << endl;

	//empty(), size()
	if (!pq.empty())
		cout << "pq size : " << pq.size() << endl;

	//pop all
	while (!pq.empty()) {
		cout << pq.top().value << " ";
		pq.pop();
	}
	cout << endl;
}