// Heap.cpp : Defines the entry point for the console application.
//

//#include "stdafx.h"

#include<iostream>
#include<string.h>
//#include<windows.h>
#include<conio.h>
#include<stdlib.h>
#include<fstream>
#include<typeinfo>
#include<fstream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <bits/stdc++.h>

using namespace std;
ifstream f("algsort.in");
ofstream g("algsort.out");



//int length=0;
// int heapsize=0;
const int MAX=100;

template<class Type> class Object
{
	Type value;
	int priority;


public:

	Object(){
	};
	template<class Ttype> Object(Ttype value1,int priority1)
	{
		value=value1;
		priority=priority1;
	}
	template<class Ttype> void SetValue(Ttype value1)
	{
		value = value1;
	}
	Type GetValue()
	{
		return value;
	}
	 void SetPriority(int priority1)
	{
		priority = priority1;
	}
	int GetPriority()
	{
		return priority;
	}
	Object* operator = (Object *nod)
	{
		this->value = nod->GetValue();
		this->priority = nod->GetPriority();

		return this;
	}

	bool operator > (Object obj)
	{
		if(this->GetPriority() > obj.GetPriority())
			return true;

		return false;
	}

	bool operator <= (Object obj)
	{
		if(this->GetPriority() <= obj.GetPriority())
			return true;

		return false;
	}


	int parent(int i)
	{return (i/2);}


	int left(int i)
	{return 2*i;}


	int right(int i)
	{return (2*i+1);}



};


template <class Type> class Heap
{
	Object<Type> a[100];


public :

	Object<Type> GetValue(int index)
	{
		return a[index];
	}

	void SetIndex(Object<Type> obj ,int index)
	{
		a[index] = obj;
	}

	void max_heapify(int i, int n)
	{
		int j;
		Object<Type> temp;

		temp = a[i];
		j = 2*i;
		while (j <= n)
		{
			if (j < n && a[j+1] > a[j])
				j = j+1;
			if (temp > a[j])
				break;
			else if (temp <= a[j])
			{
				a[j/2] = a[j];
				j = 2*j;
			}
		}
		a[j/2] = temp;
		return;
	}
	void heapsort( int n)
	{
		Object<Type> temp;
		for (int i = n; i >= 2; i--)
		{
			temp = a[i];
			a[i] = a[1];
			a[1] = temp;
			this->max_heapify(1, i - 1);
		}
	}
	void build_maxheap( int n)
	{
		int i;
		for(i = n/2; i >= 1; i--)
		{
			max_heapify(i, n);
		}
	}

	void heap_extract_min(int n)
    {
        if (n<1)
        g<<"ERROR UNDERFLOW";
       // int minimum = a[1].GetPriority();
      cout<<"Value: "<<a[1].GetValue()<<" Prior: "<<a[1].GetPriority()<<endl;
            a[1]= a[n];
        n--;
        max_heapify(1,n);
        //return minimum;
}

    bool IsChar()
	{
		const char *t = typeid(Type).name();
		if (!strcmp("char", t))
			return true;

		return false;
	}

	int CompareTo(Type firstEle ,Type lastEle) // -1 for < ; 0 for =  ; 1 for >
	{
		int rez =0;

		if (IsChar())
		{
			rez = strcmp(firstEle, lastEle);
		}
		else
		{
			if (firstEle > lastEle)
				rez = 1;
			else
			{
				if (firstEle < lastEle)
					rez = -1;
			}
		}

		return rez;
	}


};


int main()
{
	int val;
	int p;
	Object<int> d[100];

	Heap<int> h;

	int length;
	//cout<<"Enter no of elements of array";
	f>>length;
	int heapsize=length;
	for (int  i = 1; i <= length; i++)
	{
		//cout<<"Enter Value: ";
		f>>val;
		p=val;
		d[i] = new Object<int>(val,p);
		h.SetIndex(d[i],i);
	}
	h.build_maxheap(length);
	h.heapsort(length);


            for(int i=1;i<=length;i++)
    g<<h.GetValue(i).GetValue()<<" ";


    return 0;

	char op;
	do
	{
		int ch;

		cout<<"----------Menu-------------\n\n";
		cout<<"\t1.Insertion\n\t2.Extract\n\t3.Show\n\t4Find after value";
		cout<<"\n\n\tEnter your Choice<1,2,3,4> ";
		cout<<endl;
		cin>>ch;
		switch(ch)
		{
		case 1 :{  length++;
			cout<<"Enter Value: ";

			cin>>val;
			cout<<"Enter Priority (KEY): ";
			cin>>p;
			heapsize+=1;
			d[length] = new Object<int>(val,p);
			h.SetIndex(d[length],length);
			h.build_maxheap(length);
			h.heapsort(length);
			///  d[length]->heapincp(heapsize,p);
			///  d[length]->min_heap_insert(d[length]->GetPriority());
			cout<<endl;
			break;
				}

				  case 2 : {  cout<<"\n PRIORITY QUEUE \n";
				/*d[1]->heap_extract_min();
				//cout<<endl;
				// length--;
				d[1] = d[heapsize];
				heapsize--;
				d[1]->minheapify(1);
				break;
				*/
				   //  cout<<h.heap_extract_min(length)<<endl;
				     h.heap_extract_min(length);
                    length--;
				h.build_maxheap(length);
			h.heapsort(length);
				break;
				}

		case 3:{
			for(int i=1;i<=length;i++){
				Object<int> temp = h.GetValue(i);
				cout<<temp.GetValue()<<" "<<temp.GetPriority();
				cout<<endl;
			}
			cout<<endl;
			break;
			   }

    /*    case 4:
            { int index;
            cout<<"Priority order algsort: ";

                    Object<int> temp;
                  for( int j=1;j<=length;j++){
            temp = h.GetValue(1);
            for(int i=2;i<=length;i++){
                if(h.CompareTo(temp.GetValue(),h.GetValue(i).GetValue())<0){
                    temp = h.GetValue(i);
                index=i;}
                }
                cout<<h.GetValue(index).GetValue()<<" "<<h.GetValue(index).GetValue();
                temp = h.GetValue(index);
                h.GetValue(index) = h.GetValue(length);
                h.GetValue(length) = h.GetValue(index);
                  length--;
        h.max_heapify(1,length);
                            length--;
				h.build_maxheap(length);
			h.heapsort(length);
                  }
            }
            */
		}
		cout<<"\n\nDo You Want to Continue <Y/N> ?";
		cout<<endl;
		cin>>op;
	}
	while(op=='Y' || op=='y');

	return 0;

}