[백준 BOJ][C++]1927번 최소 힙 풀이: Heap

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

1927번: 최소 힙

 

 최소 힙은 루트 노드에 항상 가장 작은 원소가 위치하도록 하는 자료구조 입니다. 

 

 때문에 부모 노드는 자식 노드보다 항상 작은 값을 갖게 됩니다. 

 

 우선순위큐를 사용하여 쉽게 구현할 수 있습니다. 

 

 처음엔 scanf와 printf 대신 cin과 cout 을 사용했더니 시간 초과로 실패 했습니다. 

 

 구글링을 통해 일반적으로 scanf/printf 보다 cin/cout이 더 느리다는 점을 확인한 뒤, 성공할 수 있었습니다.  

 

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
#include<cstdio>

using namespace std;

int N;
priority_queue<int, vector<int>, greater<int>> minHeap;

void remove() {
	if (minHeap.size() == 0) {
		printf("%d\n", 0);
		return;
	}
	printf("%d\n", minHeap.top());
	minHeap.pop();
}

int main(void) {

	scanf("%d", &N);

	for (int i = 0; i < N; i++) {
		int x;
		scanf("%d", &x);

		if (x == 0)
			remove();
		else
			minHeap.push(x);
	}

	return 0;
}