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

#include <iostream>
#include <queue> // 우선순위 큐를 이용하여 쉽게 힙을 구현할 수 있다.
using namespace std;

int N, x;
priority_queue<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;
}

힙에 대해서 다시 공부해 볼 수 있는 시간이었다.
트리를 사용하여 높은 값을 트리의 부모 노드에 배치하는 그러한 완전 이진 트리의 형태를 띈다. 시험보면 무조건 나와서 아직 까먹지는 않았는데 트리를 직접 구현하라니 시간도 많이 들고 너무 막막했다...

그래서 인터넷을 조금 참고해서 문제를 풀었다.
바로 우선순위 큐를 활용하는 것이다. 우선순위 큐를 넣으면 자동으로 내림차순으로 정렬이 되기때문에 최대 힙처럼 사용이 가능하다는 것이다.

아니 어떻게 이런 생각을 하지? 사람들은 너무 똑똑해!