#include <iostream>
#include <queue> // 우선순위 큐를 이용하여 쉽게 힙을 구현할 수 있다.
#include <vector> // 오름차순 정렬 위해
using namespace std;
int N, x;
priority_queue<int, vector<int>, greater<int> > pq; // 오름차순 우선순위 큐
int main(int argc, char* argv[]){
scanf("%d",&N);
for(int i=0; i<N; i++){
scanf("%d",&x);
if(x == 0){ // 답 출력
if(!pq.empty()){
printf("%d\n", pq.top()); // front말고 top
pq.pop(); // 값 꺼내기
} else {
printf("0\n");
}
} else { // 힙에 값 넣기
pq.push(x);
}
}
return 0;
}
백준 11279 최대힙 문제와 동일한 문제.
다른점이 있다면 최소 힙(부모노드가 자식노드보다 작거나 같은 값을 가진다) 이므로
자동으로 내림차순으로 정렬되는 우선순위 큐를
priority_queue<int, vector<int>, greater<int> > pq; // 오름차순 우선순위 큐
를 사용해서 오름차순 우선순위 큐로 바꾸어서 사용하면 된다.