[BOJ] 백준 1927 최소 힙

출처: https://www.acmicpc.net/problem/1927

heap을 반복문을 이용하여 구현

※ [그래프] 힙(Heap) 자료구조란?

힙(Heap) 자료구조란?

---

#include <iostream>
using namespace std;
int heap[100001] = { 0, };
int heapSize = 0;
void swap(int A, int B) {
    int temp = heap[A];
    heap[A] = heap[B];
    heap[B] = temp;
}
 
// 상향식
void insert(int x) {
    heap[++heapSize] = x;
    int cur = heapSize;
    while (cur != 1) {
        if (heap[cur] < heap[cur / 2]) {
            swap(cur, cur / 2);
            cur /= 2;
            continue;
        }
        break;
    }
}
 
// 하향식
int pop() {
    if (heapSize == 0) return 0;
    
    int result = heap[1];
    heap[1] = heap[heapSize--];
    int cur = 1;
 
    // heap 재구성 (하향식)
    int target;
    while (cur <= heapSize) {
        // 왼쪽 자식 노드가 존재하는 경우
        if (cur * 2 <= heapSize) {
            target = cur * 2;
            // 오른쪽 자식도 존재하는 경우
            if (cur * 2 + 1 <= heapSize) {
                // 왼쪽 자식과 오른쪽 자식 노드 중 작은 노드 선택
                target = heap[cur * 2] <= heap[cur * 2 + 1] ? target : cur * 2 + 1;
            }
 
            // 자식 노드와 비교해서 swap 처리
            if (heap[cur] > heap[target]) {
                swap(cur, target);
                cur = target;
                continue;
            }
        }
        // 자식 노드가 없는 경우
        break;
    }
    return result;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
 
    int x, n; cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        if (x == 0) cout << pop() << '\n';
        else insert(x);
    }
}