[백준] 11279번 - 우선 순위 큐

#include <iostream>
#include <queue>

using namespace std;

int main() {	
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	priority_queue<int> pq;
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		if (x == 0) {
			if (!pq.empty()) {
				cout << pq.top() << '\n';
				pq.pop();
			}
			else
				cout << 0 << '\n';
		}
		else {
			pq.push(x);
		}
	}
}

 

우선 순위 큐는 데이터를 삽입할 때 자동으로 내림차순으로 정렬하여 삽입해 가장 위에 가장 큰 수가 오게 된다.

그래서 1,3,2 순서로 삽입해도 3,2,1 순서로 데이터를 뽑는다. 우선 순위 큐는 트리 구조로 보는 것이 합리적이며 

일반적으로 최대 힙을 이용한다. 

 

최대 힙에서 원소는 완전 이진 트리 형태를 유지하면서 순차적으로 밑에서 루트노드까지 거슬러 올라가면서 삽입을 진행한다. 부모 노드와 비교해서 부모 노드보다 값이 크다면 교체한다.