백준 1927 - 최소 힙

백준 1927 문제 바로가기

풀이

문제 조건에 따라 최소 힙을 구현한다.

<queue> 라이브러리에서 제공하는 priority_queue<int>를 사용해도 되고, 직접 구현해도 된다.

1. 배열에 자연수 x를 넣는다. push
2. 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다. pop

연산의 개수는 최대 $10^{5}$이다.

• x가 0이라면 pop 연산을 수행한다. 배열이 비어있는 경우 0을 출력한다.

• x가 그 이외의 수라면 push 연산을 수행한다.

• x는 $2^{31}$ 보다 작은 자연수 또는 0이다.

소스 코드

// min-heap implementation
#include <iostream>
using namespace std;

inline static void swap(int& a, int& b) {
    static int tmp;
    tmp = a;
    a = b;
    b = tmp;
}

int N;
int heap[100005];
int hs; // heap size

void push(int x) {
    heap[++hs] = x;
    for (int i = hs; i > 1 && heap[i] < heap[i >> 1]; i >>= 1) {
        // heap[i] : now(child)
        // heap[i >> 1] : parent
        // now(child) < parent : swap
        swap(heap[i], heap[i >> 1]);
    }
}

int pop() {
    if (hs == 0) return 0; // empty

    const int ret = heap[1];
    heap[1] = heap[hs--]; // last node ---move--> root node
    
    // re-build
    int t;
    for (int i = 1; (i << 1) <= hs;) {
        int left = i << 1; // heap[i]'s left
        int right = left + 1; // heap[i]'s right
        if (heap[left] < heap[right] || right > hs) {
            t = left;
        }
        else {
            t = right;
        }

        if (heap[t] < heap[i]) {
            swap(heap[t], heap[i]);
            i = t;
        }
        else {
            break;
        }
    }
    return ret;
}

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

    cin >> N;
    int x;
    for (int i = 0; i < N; ++i) {
        cin >> x;
        if (x == 0) {
            cout << pop() << '\n';
        }
        else {
            push(x);
        }
    }
    return 0;
}