[c++/백준]1927 최소 힙

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

1927번: 최소 힙

힙 구현의 가장 기초인것 같다. 

구현을 해도 되지만 STL 사용하면 더 쉽게 풀 수 있다. 

 

우선순위 큐는 삽입 순서에 상관 없이 우선순위가 가장 높은 원소가 먼저 출력되는 특징을 갖고있다. 일반적으로는 값이 가장 큰 원소가 먼저 출력이 되지만 아래와 같이 조건을 붙여주면 값이 가장 작은 원소가 먼저 출력될 수 있다. 

 

우선순위 큐의 기본 템플릿은 

priority_queue < 자료형, vector<자료형>, less<자료형> > 이다. 여기서 less는 내림차순이며 오름차순으로 하고싶다면 greater로 대체하면 된다. 

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;

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

	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;

		if (x == 0) {
			if (pQ.size() == 0) {
				cout << "0"<<'\n';
			}
			else
			{
				cout << pQ.top() << '\n';
				pQ.pop();
			}
		}
		else
		{
			pQ.emplace(x);
		}
	}
}