[알고리즘] 백준 11279 최대 힙

문제 소개

최대 힙을 구현하는 문제이다. 최대 힙에 대해서는 여러 문서에서 자세히 설명하고 있으니 넘어가겠다.
문제 해결에 필요한 함수는 총 세개이다.
push(n) : 값을 힙에 넣는다.
pop() : 값을 삭제한다.
top() : 최대 값을 읽는다.

소스코드

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

class max_hip {
private:
    int * data;
    int size;
    void swap(int & a,int & b) {
        int tmp = a;
        a = b;
        b = tmp;
    }
public:
    max_hip(int n) {
        data = new int[n+1];
        size = 0;
    }
    void push(int n) {
        data[size+1] = n;
        size++;
        for(int i = size;i/2>0;i /= 2) {
            if(data[i/2] < data[i]) {
                swap(data[i/2],data[i]);
            }
            else break;
        }
    }
    int top() {
        if(size == 0) return 0;
        return data[1]; 
    }
    void pop() {
        if(size == 0) return;
        data[1] = data[size];
        data[size] = 0;
        size--;
        int n = 2; 
        while(n <= size) {
            int tmp = data[n/2];
            int a = -1;
            if(data[n] > tmp) {
                tmp = data[n];
                a = 0;
            }
            if(data[n+1] > tmp) {
                tmp = data[n+1];
                a = 1;
            }
            if(a == -1) break;
            swap(data[n/2],data[n+a]);
            n = (n+a) * 2;
        }
    }

};

int main() {
    max_hip * hip;
    int n;
    scanf("%d",&n);
    hip = new max_hip(n);
    while(n--) {
        int tmp;
        scanf("%d",&tmp);
        if(tmp == 0) {
            printf("%d\n",hip->top());
            hip->pop();
        }
        else hip->push(tmp);
    }
    
}