[C++] C++ STL priority_queue 기본 사용법과 예제
C++에서 priority_queue 사용법을 간단하게 알아보자
환경 및 선수조건
- C++
우선순위 큐 기본 함수
기본형태
priority_queue<T, Container, Compare>: 원하는 자료형 및 클래스 T를 통해 생성. 여기서 Container는 vector와 같은 컨테이너이며 Compare는 비교함수 클래스이다.
추가 및 삭제
push(element): 우선순위 큐에 원소 추가pop(): 우선순위 큐에서 top의 원소를 삭제
조회
top(): top에 있는 원소를 반환
기타
empty(): 비어있으면 true 아니면 false를 반환size(): 우선순위 큐에 포함되어 있는 원소들의 수를 반환
구현 코드(Max Heap)
#include <iostream>
#include <functional>
#include <queue>
using namespace std;
int main(){
// priority_queue
priority_queue< int, vector<int>, less<int> > pq;
// or priority_queue<int> pq;
// push(element)
pq.push(5);
pq.push(2);
pq.push(8);
pq.push(9);
pq.push(1);
pq.push(14);
// pop()
pq.pop();
pq.pop();
// top();
cout << "pq top: " << pq.top() << '\n';
// empty(), size()
if(!pq.empty()) cout << "pq size: " << pq.size() << '\n';
// pop all
while(!pq.empty()){
cout << pq.top() << " ";
pq.pop();
}
cout << '\n';
return 0;
}
구현 코드(Min Heap)
#include <iostream>
#include <functional>
#include <queue>
using namespace std;
int main(){
// priority_queue
priority_queue< int, vector<int>, greater<int> > pq;
// push(element)
pq.push(5);
pq.push(2);
pq.push(8);
pq.push(9);
pq.push(1);
pq.push(14);
// pop()
pq.pop();
pq.pop();
// top();
cout << "pq top: " << pq.top() << '\n';
// empty(), size()
if(!pq.empty()) cout << "pq size: " << pq.size() << '\n';
// pop all
while(!pq.empty()){
cout << pq.top() << " ";
pq.pop();
}
cout << '\n';
return 0;
}
구현 코드(만든 구조체와 비교함수 이용)
#include <iostream>
#include <queue>
using namespace std;
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;
}
};
// 아래와 같이 class로도 작성이 가능합니다.
class CompareFunctionObject
{
public:
int operator()(Custom t, Custom u){
return t.value > u.value;
}
};
int main(){
// priority_queue
priority_queue< Custom, vector<Custom>, cmp > pq;
// 아래는 class 사용 시 예제
// priority_queue< Custom, vector<Custom>, CompareFunctionObject > pq;
// 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 << '\n';
// empty(), size()
if(!pq.empty()) cout << "pq size: " << pq.size() << '\n';
// pop all
while(!pq.empty()){
cout << pq.top().value << " ";
pq.pop();
}
cout << '\n';
return 0;
}