1. 문제설명

자료구조 중 최소 힙을 구현하는 문제
N개의 원소가 주어진다.
0이 입력되면 최소값을 출력하고, 그 값을 제거한다.
- 이외의 값은 최소 힙에 넣는다.

2. 알고리즘 설계

STL 중 priority_queue(pq)가 heap 구조이다.
단, pq는 max heap 이므로, operator 오버로딩 필요

3. 로직

operator를 지정해 min heap을 만들면 된다.

struct comp {
	bool operator()(int a, int b) {
		return a > b;
	}
};

4. 전체 코드

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

struct comp {
	bool operator()(int a, int b) {
		return a > b;
	}
};

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

	priority_queue<int, vector<int>, comp> pq;
	int n; cin >> n;

	while (n--) {
		int temp; cin >> temp;
		if (temp == 0) {
			if (pq.empty()) {
				cout << 0 << '\n';
				continue;
			}
			cout << pq.top() << '\n';
			pq.pop();
		}
		else
			pq.push(temp);
	}
	return 0;
}

5. 소감

priority_queue<int, vector<int>, comp> pq;를 사용하기엔 너무 귀찮다.
다른 사람 코드에서 매우 간단한 풀이법을 보았다.
- 핵심은, pq의 default가 max heap이라는 것
```
priority_queue<int> pq;
pq.push(~n);
...
cout << ~pq.top() << '\n';
```
-는 안전하지 않다. (물론 이 문제는 상관없긴 하다.)
- 자료형의 최대 범위의 절대값이 1이 차이나긴 때문
- algorithm repo의 issue에 자세히 설명하였다.

BOJ 1927. 최소 힙

1. 문제설명

2. 알고리즘 설계

3. 로직

4. 전체 코드

5. 소감