[C++] 백준 1927번 최소 힙

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

풀이

우선순위 큐는 기본적으로 최대 힙이지만, 비교 함수로 greater을 넣어주면 최소 힙을 구현할 수 있다.

최소 힙

priority_queue<int, vector<int>, greater<int>> min_heap;

정렬 vs 우선순위 큐

less (기본값)

• sort: 오름차순
• priority_queue: 최대 힙

greater

• sort: 내림차순
• priority_queue: 최소 힙

코드

#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, vector<int>, greater<int>> heap;
    while(n--){
        cin >> x;
        
        if(x == 0) {
            if(heap.empty()) cout << "0\n";
            else {
                cout << heap.top() << "\n";
                heap.pop();
            }
        }
        else heap.push(x);
    }
    
    return 0;
}