[백준] 1927번: 최소 힙 C++

 

설명)

최소힙은 완전 이진트리로 구현된 데이터 구조이며, 우선순위 큐를 이용하면 쉽게 구현할 수 있습니다. 

특징은 다음과 같습니다.

 

 

특징)

루트 노드(Top):

항상 힙의 최솟값을 유지합니다.

 

부모-자식 관계:

부모 노드의 값은 항상 자식 노드의 값보다 작거나 같아야 합니다.

즉, 트리의 모든 부모-자식 관계에서 부모 ≤ 자식이 성립합니다.

 

정렬 상태:

힙은 전체적으로 정렬된 구조는 아니지만, 최솟값을 빠르게 찾는 데 최적화된 형태로 정렬되어 있습니다.

 

또 앞으로 글을 작성하겠지만 이 우선순위 큐는 다익스트라 알고리즘에서도 사용되기 때문에 지금 사용법을 잘 익혀 두면 좋습니다.

코드는 다음과 같습니다.

 

코드)

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

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

    int n;
    cin >> n;

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

    while (n--) {
        int x;
        cin >> x;

        if (x == 0) {
            if (pq.empty()) {
                cout << 0 << '\n';
            }
            else {
                cout << pq.top() << '\n';
                pq.pop();
            }
        }
        else {
            pq.push(x);
        }
    }

}