#include <iostream>

#define 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-арной кучи*/
template <class Item>
void d_ary_fixUp(Item a[], int node){
	while(node > 1 && a[(node - 1)/d] < a[node]){
		std::swap(a[node], a[(node - 1)/d]);
		node = (node - 1) / d;
	}
}

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

		if(j < n && a[j] < a[j + 1]) j++;
		if(!(a[node] < a[j])) break;
		std::swap(a[node], a[j]);
		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_fixDown(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;
}