Priority Queue using array based Heap

 

2751번: 수 정렬하기 2

#include <bits/stdc++.h>
#define endl '\n'
 
using namespace std;
 
class Heap
{
private:
    int* arr;
    int n;
    int N;
 
public:
    Heap() = delete;
    Heap(int N) : arr{new int[N+1]}, n{0}, N{N} {}
    ~Heap();
    int size() const { return n; }
    bool empty() const { return n == 0; }
    void push(int x);
    int pop();
};
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    int N; cin >> N;
    Heap hp{N};
    for(int i = 0; i < N; i++){
        int tmp; cin >> tmp;
        hp.push(tmp);
    }
 
    for(int i = 0; i < N; i++){
        cout << hp.pop() << endl;
    }
 
    return 0;
}
 
Heap::~Heap()
{
    if(arr != nullptr){
        delete arr; arr = nullptr;
    }
}
 
void Heap::push(int x)
{
    if(n == N) throw "full";
 
    n += 1;
    arr[n] = x;
    for(int i = n; i > 1; i /= 2){
        if(arr[i] < arr[i/2]) swap(arr[i], arr[i/2]);
        else break;
    }
}
 
int Heap::pop()
{
    if(empty()) throw "empty";
 
    int ret = arr[1];
    arr[1] = arr[n];
    int p = 1;
    while(2*p <= n){
        int nxt = 2*p;
        if(2*p + 1 <= n && arr[2*p] > arr[2*p+1]) nxt += 1;
        if(arr[p] < arr[nxt]) break;
        else{
            swap(arr[p], arr[nxt]);
            p = nxt;
        }
    }
 
    n -= 1;
    return ret;
}cs