Priority Queue using Linked Heap

 

2751번: 수 정렬하기 2

#include <iostream>
#include <string>
#define endl '\n'
 
using namespace std;
 
class Node
{
private:
    Node *parent, *left, *right;
    int elem;
 
public:
    Node() = delete;
    Node(int elem) : elem{elem} { parent = left = right = nullptr; }
    ~Node() = default;
    friend class Heap;
};
 
class Heap
{
private:
    Node *root, *last;
    int n; // size
    void release(Node* node);
    void upheap(Node* node);
    void downheap(Node* node);
    void swap_element(Node* u, Node* v);
 
public:
    Heap() : n{0} { root = last = nullptr; }
    ~Heap() { if(root != nullptr) release(root); }
    int size() const { return n; }
    bool empty() const { return n == 0; }
    int top() const;
    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{};
    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;
}
 
void Heap::downheap(Node* node)
{
    while(node->left != nullptr){
        Node* nxt = node->left;
        if(node->right != nullptr && node->left->elem > node->right->elem) nxt = node->right;
        if(node->elem < nxt->elem) break;
        else{
            swap_element(node, nxt);
            node = nxt;
        }
    }
}
 
void Heap::swap_element(Node* u, Node* v)
{
    int tmp = v->elem;
    v->elem = u->elem;
    u->elem = tmp;
}
 
void Heap::upheap(Node* node)
{
    while(node->parent != nullptr){
        if(node->parent->elem > node->elem){
            swap_element(node, node->parent);
            node = node->parent;
        }
        else break;
    }
}
 
void Heap::release(Node* node)
{
    if(node->left != nullptr) release(node->left);
    if(node->right != nullptr) release(node->right);
    delete node; node = nullptr;
}
 
int Heap::top() const
{
    if(empty()) throw "empty";
 
    return root->elem;
}
 
void Heap::push(int x)
{
    Node* node = new Node{x};
    if(empty()) root = last = node;
    else{
        while(last->parent != nullptr && last->parent->left != last)last = last->parent;
 
        if(last->parent != nullptr && last->parent->right == nullptr){
            node->parent = last->parent;
            last->parent->right = node;
        }
        else{
            if(last->parent != nullptr) last = last->parent->right;
            while(last->left != nullptr) last = last->left;
            last->left = node;
            node->parent = last;
        }
        last = node;
        upheap(last);
    }
    
    n += 1;
}
 
int Heap::pop()
{
    if(empty()) throw "empty";
 
    int ret = root->elem;
    swap_element(root, last);
    Node*rm = last;    
    if(rm->parent == nullptr){
        root = last = nullptr;
    }
    else{
        while(last->parent != nullptr && last->parent->right != last) last = last->parent;
        if(last->parent != nullptr && last->parent->left != nullptr) last = last->parent->left;
        while(last->right != nullptr) last = last->right;
 
        if(rm->parent->left == rm) rm->parent->left = nullptr;
        else rm->parent->right = nullptr;
        downheap(root);
    }
 
    n -= 1;
    delete rm; rm = nullptr;
 
    return ret;
}cs