[C++] 백준 11279번 최대 힙

https://www.acmicpc.net/problem/11279

풀이

우선순위 큐 자료구조를 이용하였다.

우선순위 큐

priority_queue를 이용하려면 #include <queue> 문을 써줘야 한다.

• push(n): n의 우선순위에 따라 삽입
• pop(): 우선순위가 가장 큰 요소 제거
• top(): 우선순위가 가장 큰 요소 반환
• empty(): 우선순위 큐가 비어있는지 여부 반환
• size(): 우선순위 큐의 크기 반환

최대 힙

priority_queue<int, vector<int>, less<int>> max_heap;

우선순위 큐는 기본적으로 최대 힙을 구현하므로, 최대 힙을 사용할 때는 아래와 같이 써도 된다.

priority_queue<int> max_heap;

코드

#include <iostream>
#include <queue>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n, x;
    cin >> n;
    
    priority_queue<int> heap;
    while(n--){
        cin >> x;
        if(x) heap.push(x);
        else if(heap.empty()) cout << "0\n";
        else{
            cout << heap.top() << "\n";
            heap.pop();
        }
    }
    
    return 0;
}