[BOJ-11286]절대값 힙

https://www.acmicpc.net/problem/11286

[문제설명]

cmd 입력으로 0이 아닌 입력이 들어오면 원소를 넣는다.

cmd 입력이 0 인 경우 힙의 가장 위에 있는 원소를 출력한다.

이때 힙에 가장 위에 위치는 원소는 절대값으로 가장 작고, 동일한 절대값이 있는 경우 가장 작은 값을 출력한다.

이때 힙이 비어있는 경우 0을 출력한다. 

[문제풀이]

힙을 구현하면 된다. 

이때 minheap을 구현하기 위해서 node라는 구조체를 선언하고 operator < 로 비교하게 하여 조건을 처리하여 풀이할 수 있다.

[C++ source code]

#include<iostream>
#define din(a) scanf("%d", &a)
 
inline int my_abs(int a) {
    return (a > 0) ? a : -a;
}
 
struct node {
    int d;
    node() { d = 0; }
    node(int i):d(i){}
    bool operator < (node t) {
        if (my_abs(d) == my_abs(t.d)) {
            if (d < t.d) return true;
            return false;
        }
        else if (my_abs(d) < my_abs(t.d)) {
            return true;
        }
        return false;
    }
};
 
template<typename T>
struct heap {
    T d[1 << 18];
    int e;
    heap() {
        e = 0;
    }
    bool empty() {     return !e; }
    bool full() { return (e + 1) == (1 << 18); }
    void push(T input) {
        if (full()) return;
        d[++e] = input;
        int cur = e;
        while ((cur / 2) > 0) {
            if (d[cur] < d[cur / 2]) {
                swap(d[cur], d[cur / 2]);
            }
            else {
                break;
            }
            cur /= 2;
        }
    }
    void pop() {
        if (empty()) return;
        d[1] = d[e];
        e--;
        //d[e--].clear();
        int cur = 1;
        while (cur * 2 <= e) {
            int child;
            if (cur * 2 + 1 > e) {
                child = cur * 2;
            }
            else {
                if (d[cur * 2] < d[cur * 2 + 1]) {
                    child = 2 * cur;
                }
                else {
                    child = 2 * cur + 1;
                }
            }
 
            if (d[cur] < d[child]) {
                break;
            }
            swap(d[cur], d[child]);
            cur = child;
        }
    }
    T top() {
        T ret;
        if (empty()) return ret;
        return d[1];
    }
    void swap(T& a, T& b) {
        T t = a;
        a = b;
        b = t;
    }
};
 
heap<node> PQ;
int main() {
    int OP;
    din(OP);
    for (register int i = 0; i < OP; ++i) {
        int cmd;
        din(cmd);
         if (cmd == 0) {
            if (PQ.empty()) {
                puts("0");
            }
            else {
                printf("%d\n", PQ.top().d);
                PQ.pop();
            }
        }
        else {
            PQ.push(node(cmd));
        }
    }
    return 0;
}