1주차(자료구조) - [C++]백준1927 최소 힙

07 Mar 2022 in Study on Algorithm

백준1927 최소 힙 링크

문제

예제 입력

---

코드

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

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int N;
	cin >> N;

    // priority_queue< int, vector<int>, greater<int> > heap; 최소 힙
	priority_queue<int> heap;
	int num;
	for (int i = 0; i < N; i++) {
		cin >> num;
		if (num == 0) {
			if (heap.empty())
				cout << 0 << "\n";
			else {
				cout << -heap.top() << "\n";
				heap.pop();
			}
		}
		else
			heap.push(-num);
	}
}

설명

C++ STL(표준 템플릿 라이브러리)에서 우선순위 큐는 기본적으로 최대값을 TOP으로 만들어지지만 비교함수를 통해서 최소값을 TOP으로 하는 최소 힙을 만들수 있습니다. 하지만 저는 최대 힙의 값을 PUSH할때와 TOP할때 보수로 만들어서 구현했습니다.

<queue>
-priority_queue<자료형, 자료형태, 비교함수> 변수명; : 우선순위 큐(힙) 자료구조 사용
<비교함수>
-greater<자료형> : 내림차순 정렬
-less<자료형> : 오름차순 정렬

---

결과