pop 할 때 가장 먼저 들어온 원소가 나오는 대신 우선순위가 가장 높은 원소가 나오는 큐

1. 원소의 추가가 O(lg N)
2. 우선순위가 가장 높은 원소의 확인이 O(1)
3. 우선순위가 가장 높은 원소의 제거가 O(lg N)

우선순위 큐와 힙의 관계

• set 보다 수행 속도가 빠르고, 메모리 공간도 적게 차지함

STL 우선순위 큐

BOJ 연습문제

#include <bits/stdc++.h>

using namespace std;

class cmp{
	public : 
		bool operator() (int a, int b){
			if(abs(a) != abs(b)) return abs(a) > abs(b);
			return a > 0 && b < 0;
		}
};

int main(){
	priority_queue<int, vector<int>, cmp> pq;
	int n;
	cin >> n;
	while(n--){
		int x;
		cin >> x;
		if(x == 0){
			if(pq.empty()) cout << "0\\n";
			else{
				cout << pq.top() << '\\n';
				pq.pop();
			}
		}
		else pq.push(x);
	}
}