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

알고리즘/백준

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

이민훈 2021. 4. 21. 05:42

www.acmicpc.net/problem/1927

1927번: 최소 힙

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0

www.acmicpc.net

풀이

최소 힙을 구현하는 문제입니다.

#include<iostream>

using namespace std;

const int MAX = 100001;

class MinHeap
{
private:
    int heap[MAX];
    int idx = 0;
public:
    int size();
    void push(int data);
    int pop();
    void swap(int* a, int* b);
    int select(int child);
};

int MinHeap::size()
{
    return idx;
}

void MinHeap::push(int data)
{
    heap[++idx] = data;

    int child = idx;
    int parent = child / 2;
    while (child > 1 && heap[child] < heap[parent]) {
        swap(&heap[child], &heap[parent]);
        child = parent;
        parent = child / 2;
    }
}

int MinHeap::pop()
{
    int ret = heap[1];

    swap(&heap[idx--], &heap[1]);

    int parent = 1;
    int child = parent * 2;
    child = select(child);

    while (child <= idx && heap[parent] > heap[child]) {
        swap(&heap[parent], &heap[child]);
        parent = child;
        child = child * 2;
        child = select(child);
    }

    return ret;
}

void MinHeap::swap(int* a, int* b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

int MinHeap::select(int child)
{
    if (child + 1 <= idx) child = (heap[child] < heap[child + 1]) ? child : child + 1;
    return child;
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    MinHeap h;

    int n; cin >> n;

    while (n--) {
        int c; cin >> c;
        if (c == 0) {
            if (h.size()) cout << h.pop();
            else cout << 0;
            cout << '\n';
        }
        else h.push(c);
    }

    return 0;
}

반례

Input

15
1
77
10000
9923
24
0
1533
4123
0
51
2
8
0
0
0

Output

저작자표시