1927번-최소 힙

중요 지식

---

힙 - 빠르게 최소값을 찾기 위함

코드

---

#include <iostream>

using namespace std;

typedef struct heap{
    int arr[100001];
    int size;
} heap;

void initHeap(heap *hp){
    hp->size = 0;
}

void swap(int *a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}

void insert(heap *hp, int data){
    int here = ++hp->size;

    while(here!=1 && data < hp->arr[here/2]){
        hp->arr[here] = hp->arr[here/2];
        here /= 2;
    }
    hp->arr[here] = data;
}

int deleteData(heap *hp) {
    if (hp->size == 0) return 0;
    int ret = hp->arr[1];
    hp->arr[1]=hp->arr[hp->size--];
    int parent = 1;
    int child;
 
    while (1) {
        child = parent * 2;
        if (child + 1 <= hp->size && hp->arr[child]>hp->arr[child + 1])
            child++;
 
        if (child>hp->size||hp->arr[child] > hp->arr[parent]) break;
         
        swap(&hp->arr[parent], &hp->arr[child]);
        parent = child;
    }
     
    return ret;
     
}

int main(){
    int N;
    heap *hp = new heap;

    cin >> N;

    initHeap(hp);

    for(int i = 0; i < N; i++){
        int x;
        scanf("%d", &x);

        if(x == 0){
            printf("%d\n", deleteData(hp));
        }else{
            insert(hp, x);
        }
    }

    return 0;
}

풀이

---

힙을 활용해서 풀면 된다