#include "list.h"
#include "Key.h"

template <class List_entry>
class priority_queue:public List<List_entry>
{
public:
	void insert_queue(const List_entry &current, int low, int high);
	void build_queue();
	void outputqueue();
	void queue_sort();
private:
Key Keyinput;

};

template <class List_entry>
void priority_queue<List_entry>::outputqueue()
{
	cout<<entry[0];
	entry[0]=0;
}

template <class List_entry>
void priority_queue<List_entry>::insert_queue(const List_entry &current, int low, int high)
{
	int large;
	large=2*low+1;
		while(large<=high)
		{
			if (large<high && entry[large] < entry [large+1])
			{
				large++;
			}
			if (current >=entry[large])
				break;
			
			else
			{	
				entry[low]=entry[large];
				low=large;
				large=2*low+1;
			}
		}
		entry[low]=current;
}

template <class List_entry>
void priority_queue<List_entry>::queue_sort()
{
   List_entry current;    
   int last_unsorted; 
   build_queue();     
   for (last_unsorted = count - 1; last_unsorted > 0; last_unsorted--) 
   {
      current = entry[last_unsorted];   
      entry[last_unsorted] = entry[0];    
      insert_queue(current, 0, last_unsorted - 1);     
   }
}


template <class List_entry>
void priority_queue<List_entry>::build_queue()
{
	int low;
	for (low=count/2-1; low>=0; low--)
	{
		List_entry current=entry[low];
		insert_queue(current, low , count-1);
	}
}