#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std;

struct Heap
{
	int* a;
	static const int MAX = 100000;
	int size;
	
	Heap( int* x , int sz )
	{
		size = sz;
		a = new int[MAX + 1];
		for (int i=1  ; i<=sz ; i++)
			a[i] = x[i];
	}
	
	void BuildHeap()
	{
		int p = size / 2;
		for ( int i=p ; i>=1 ; i--)
			Heapify(i);
	}
	
	void Heapify(int i)
	{
		while (true)
		{
			int l = i*2;
			int r = i*2+1;
			int g = i;						// farz konim kuchiktarin adad pedare
			
			if ( l<=size && a[l]<a[g] ) g = l;		// farzande chap kuchiktare ?
			if ( r<=size && a[r]<a[g] ) g = r;		// farzande rast kuchiktare ?
			
			if ( g != i )					// yeki az farzanda kuchiktar az pedare
			{
				swap(a[i],a[g]);
				i = g;
			}
			else							// pedar kuchiktar az farzandashe ya farzandi nadare -> pas nemishe bishtar az in edame dad
				break;
		}
	}
	
	void DecreaseValue(int p , int val)
	{
		if ( p < 1 || p > size ) return ;
		if ( val > a[p] ) return;
		
		a[p] = val;
		while ( p>1 )
		{
			if ( a[p] < a[p/2] )
			{
				swap(a[p] , a[p/2]);
				p = p/2;
			}
			else
				break;
		}
	}
	
	void Insert(int val)
	{
		// Check Kardane Size Arraye
		size++;
		a[size] = val;
		DecreaseValue( size , val );
	}
	
	int Delete()
	{
		if (size < 1) return -1; 
		int copy = a[1];
		swap(a[size] , a[1]);
		size--;
		Heapify(1);
		
		// Check Kardane Size Arraye
		return copy;
	}
	
	/*void Heapify(int p)
	{
		
		while (true)
		{
			int l = p*2;
			int r = p*2 + 1;
			
			if (l > size && r > size) break;
			
			int vl , vr;
			if ( r > size )
			{
				if ( a[l] < a[p] )
				{
					swap(a[l] , a[p]);
					p = l;
				}
				else
					break;
			}
			else
			{
				int v = a[l]<a[r] ? a[l] : a[r];
				if ( a[p] < v ) break;
				if ( a[l]<a[r] )
				{
					swap(a[l] , a[p]);
					p = l;
				}
				else
				{
					swap(a[r] , a[p]);
					p = r;
				}
			}
		}
		
	}*/
	
	void Print()
	{
		for (int i=1 ; i<=size ; i++)
			cout<<a[i]<<" ";
	}
	
	void PrintLikeHeap()
	{
		cout<<"\n\n";
	
		const int SIZE = 4;									// Size of every number
		int h = log(size)/log(2) + 1;						// Height of tree
		int* t = new int[h+1];								// For save 2 powers
		
		for (int i=0,p=1 ; i<=h ; t[i]=p , i++ , p*=2);		// t[0] = 2^0 , t[1] = 2^1 , ...
		
		for (int i=0 ; i<t[h]*SIZE ; i++)					// Splitter !!!
			cout<<"_";
		cout<<"\n\n";
		
		for (int i=h-1,j=0,k=1 ; i>=0 && k<=size ; i--,j++)
		{
			int c = t[j];									// Num of numbers in current row
			int out_space = t[i];							// Space of left side
			int in_space  = (t[i+1]-1);						// Space between numbers
			
			cout<<left<<setw(out_space*SIZE)<<" ";
			for (int u=0 ; u<c && k<=size ; u++,k++)			// Print a row
			{
				cout<<setw(SIZE);
				if (u%2)	cout<<right<<a[k];
				else		cout<<left<<a[k];
				cout<<setw(in_space*SIZE)<<" ";
			}
			cout<<"\n";
			
			if (i)	// Lines
			{
				bool shift = true;									// Print line or space ?
				int  counter = (t[i] + 1);							// Num of prints
				cout<<setw(out_space/2 * SIZE)<<" ";
				for (int u=0 ; u<t[h] ; u++)
				{
					for (int y=0 ; y<SIZE ; y++)
						cout<<(shift ? '-' : ' ');
					if ( --counter==0 )								// Change shift!
					{
						shift = !shift;
						counter = (shift ? t[i]+1 : t[i]-1);
					}
				}
			}
			
			cout<<"\n";
		}
	}
};

int main()
{
	int a[10] = { 0 , 126 , 18 , 24 , 1000 , 25 , 5 , 125 , 26 , 23 };
	Heap h(a , 9);
	
	// int a[21] = { 0 , 126 , 18 , 24 , 1000 , 25 , 5 , 125 , 26 , 23 , 41 , 78 , 75 , 14 , 15 , 18 , 19 , 20 , 22 , 36 , 40 };
	// Heap h(a , 20);
	
	h.BuildHeap();
	h.Print();
	h.PrintLikeHeap();
	
	h.Insert(70);
	h.Insert(62);
	h.Insert(1);
	h.PrintLikeHeap();
	
	while ( true )
	{
		int x = h.Delete();
		if ( x == -1 ) break;
		cout<<x<<" ";
	}
	cout<<"\n";
	
	return 0;
}