Baekjoon 1927 (최소 힙)

Baekjoon 1927, 백준 1927 문제의 본인 풀이입니다!
문제는 아래의 링크에서 확인할 수 있습니다.
문제보기

#include <cstdio>
#include <algorithm>
#define SWAP(a,b,type) do{ \
    type temp; \
    temp=a; \
    a=b; \
    b=temp; \
}while(0)

using namespace std;

// make heap
long long int arr[100002] = {0,};
int size = 0;

// input number
void push_heap(long long int x){
    // put number in the back
    size++;
    arr[size] = x;
 
    // sort the heap
    int child = size, parent = child/2;
    while(parent >= 1) {
        if(arr[child] < arr[parent]){
            SWAP(arr[child], arr[parent], long long int);
            child /= 2;
            parent = child/2;
        }
        else break;
    }
}

// pop min number
void pop_heap(){
    if(size == 0) {
        printf("0\n");
        return;
    }

    long long int min_num = arr[1];
    arr[1] = arr[size];
    arr[size] = 0;
    size--;                 // copy the last value to the top, and delete

    // sort heap
    int parent = 1;
    while(parent * 2 <= size) {
        // compare the parent node with two childs
        // you should have two childs

        if(arr[parent] > min(arr[parent*2], arr[parent*2 +1]) && arr[parent*2+1] != 0 ) {
            // swap with the smaller child
            if(arr[parent*2] < arr[parent*2+1]) {
                SWAP(arr[parent], arr[parent*2], long long int);
                parent = parent * 2;
            }

            else {
                SWAP(arr[parent], arr[parent*2+1], long long int);
                parent = parent * 2 + 1;
            }
        }

        // if you have only one child
        else if(arr[parent] > arr[parent*2] && arr[parent*2+1] == 0 ) {
            SWAP(arr[parent], arr[parent*2], long long int);
            parent = parent * 2;
        }

        else break;
    }

    // print min number
    printf("%lld\n",min_num);
}

int main() {

    int N;
    scanf("%d",&N);
    long long int brr[N];
    for(int i = 0; i < N; i++){
        scanf("%lld",&brr[i]);
        if(brr[i]==0) pop_heap();
        else push_heap(brr[i]);
    }
}

최소 Heap을 배열을 이용하여 직접 구현하여 해결한 우선순위-큐 문제.