#include <iostream>

const int d = 3;    /*Арность кучи*/

/*Реализация функций перестроения бинарной кучи*/
template <class Item>
void fixUp(Item a[], int node){
    while(node > 1 && a[node/2] < a[node]){
        std::swap(a[node], a[node/2]);
        node = node / 2;
    }
}

template <class Item>
void fixDown(Item a[], int node, int n){
    while(2*node <= n){
        int j = 2*node;

        if(j < n && a[j] < a[j + 1]) j++;
        if(!(a[node] < a[j])) break;
        std::swap(a[node], a[j]);
        node = j;
    }
}

/*Реализация функций перестроения d-арной кучи*/
/*
first_child = node * d + 1 - (d - 1)
last_child  = node * d + 1
parent      = (node + d - 2) / d
*/
template <class Item>
void d_ary_fixUp(Item a[], int node){
    while(node > 1 && a[(node + d - 2)/d] < a[node]){
        std::swap(a[node], a[(node + d - 2)/d]);
        node = (node + d - 2) / d;
    }
}

template <class Item>
void d_ary_fixDown(Item a[], int node, int n){
    int first_child = node*d + 1 - (d - 1);
    int last_child = node*d + 1;
    int max_child = first_child;    /*Начнем с самого первого*/

    while(d*node <= n){
        /*Находим максимального потомка*/
        for(int i = first_child; i <= last_child; i++)
            if(a[i] > a[max_child])
                max_child = i;
        /*Если он больше родителя, меняем их местами*/
        if(a[max_child] > a[(max_child + d - 2) / d])
            std::swap(a[max_child], a[(max_child + d - 2) / d]);
        node = max_child;
    }
}

template <class Item>
void d_ary_fixDown2(Item a[], int node, int n){
    int first_child = node*d + 1 - (d - 1);
    int last_child = node*d + 1;
    int max_child = first_child;    /*Начнем с самого первого*/

    while(node*d + 1 - (d - 1) <= n){
        int j = node*d + 1 - (d - 1);

        /*Ищем максимального потомка среди всех d потомков узла node*/
        for(int i = first_child; i <= last_child; i++)
            if(a[i] > a[max_child])
                max_child = i;
        /*Если потомок max_child больше своего родителя, то меняем их местами*/
        //if(a[max_child] > a[(max_child + d - 2) / d])
        if(a[max_child] > a[node])
            std::swap(a[max_child], a[node]);

        node = max_child;
        first_child = node*d + 1 - (d - 1);
        last_child = node*d + 1;
    }
}

template <class Item>
class PQ{
private:
    Item *pq;
    int n;
public:
    PQ(int max){
        pq = new Item[max + 1];
        n = 0;
    }

    ~PQ(){
        delete[] pq;
    }

    int empty() const{
        return n == 0;
    }

    void insert(Item item){
        pq[++n] = item;
        d_ary_fixUp(pq, n);
        /*Выводим состояние массива*/
        std::cout << std::endl;
        for(int i = 1; i <= n; i++)
            std::cout << pq[i] << " ";
        std::cout << std::endl;
    }

    Item getmax(){
        if(!empty()){
            std::swap(pq[1], pq[n]);
            d_ary_fixDown2(pq, 1, n-1);
            return pq[n--];
            /*Выводим состояние массива*/
            std::cout << std::endl;
            for(int i = 1; i <= n; i++)
                std::cout << pq[i] << " ";
            std::cout << std::endl;
        }else
            return 0;
    }
};

int main(){
    PQ<int> pq(50);
    int p;

    for(int i = 0; i < 10; i++)
        pq.insert(i);
    for(int i = 0; i < 10; i++)
        std::cout << pq.getmax() << " ";
    std::cin >> p;
}