Priority Queue

1. priority queue

• 우선순위 큐를 구현한 것.
• vector, deque와 붙어서 사용가능.
• default : vector container 기반 / 내림차순(less<>) 
• <queue> 헤더파일 안에 구현되어 있음.

2. 생성자

• 템플릿으로 구현되어 있음. 따라서 내부 구조나 정렬기준을 변경할 수 있음.
• priority_queue <int> pq;
• priority_queue <int, deque<int>> pq;
• priority_queue <int, vector<int>, greater<int>> pq;

3. 멤버함수

• bool empty() const : empty(true) not(false)
• size_type size() const : return size
• const value_type & top() const : 맨 위의 원소를 참조
• void push(const value_type& val) : 인자 삽입
• void pop() : 맨 위의 원소를 삭제 / 내부적으로 pop_heap() 과 pop_back() 이 사용되어 우선순위 큐의 형태를 유지

4. 간단한 응용

• min heap : priority_queue<int, vector<int>, greater<int>> min_heap;
• max heap : priority_queue<int, vector<int>, less<int>> max_heap;
• 만약 자료형으로 pair<a,b>가 들어간다면, a의 값이 같다면 b의 값을 비교해서 우선순위 결정.
• push 또는 pop의 시간복잡도는 O(logN)