[C++] 11279 최대 힙

우선순위 큐

큐에 있는 모든 원소 중에서 가장 큰 값이 Top을 유지하도록, 우선순위가 가장 크도록 설계되어 있다 또한 우선순위 큐는 내부적으로 Heap이라는 자료구조를 사용하고 있다.

큐랑 사용법이 비슷하다.
자꾸 front랑 top이랑 헷갈리는데 얘는 덱이 아니니까 back이 없음! top이다.

문제

널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

배열에 자연수 x를 넣는다.
배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.

-> 우선순위 큐를 사용하면 자연히 제일 큰 숫자가 top이 되도록 정렬되므로 우선순위 큐를 출력하면 된다.

정답

#include <iostream>
#include <queue>

using namespace std;

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

    return 0;
}