#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;
		/*Сравним значение node со значнием, которое получается вычислением родителя 
		max_child и должно равняться node*/
		std::cout << " node = " << node << " node = " << ((max_child + d - 2) / d) << std::endl;
		/*Если потомок max_child больше своего родителя, то меняем их местами*/
		if(a[max_child] > a[(max_child + d - 2) / d])
			std::swap(a[max_child], a[(max_child + d - 2) / d]);

		node = j;
	}
}

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);
	}

	Item getmax(){
		if(!empty()){
			std::swap(pq[1], pq[n]);
			d_ary_fixDown2(pq, 1, n-1);
			return pq[n--];
		}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;
}