#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>
#include <iomanip.h>
#include<time.h> 
 
template <typename type> class Heap{
   public:
 
		Heap(int IntArray[], int Count);
 
        Heap(int MAXSIZE);
 
        type Delete();
 
		void Insert(type Item);
 
		type FindMax();
 
		type FindMin();
 
		bool IsEmpty(){ //IS EMPTY FUNCTION
			return HeapSize == 0;
		}
 
        void SORT(type IntAarray[], int MAX);	
 
		void  Remove(type item);
 
		type operator[](int index){
			return HeapArrayPtr[index];
		}
 
	private:
 
      type * HeapArrayPtr;   // pointer to array holding the heap data
 
      int MaxHeapSize;
 
      int HeapSize;
 
      void FilterDown(int StartIndex);
 
      void FilterUp(int StartIndex);
 
      int Parent(int CurrentIndex){
		return (CurrentIndex - 1) / 2;
      }
 
      int RightChild(int CurrentIndex){
		return 2 * (CurrentIndex + 1);
	  }
 
      int LeftChild(int CurrentIndex){
		return 2 * CurrentIndex + 1;
	  }
 
};
 
//consrurctors
template <typename type> Heap<type>::Heap(int MAXSIZE){
 
	int *HeapArrayPtr = new int[MAXSIZE] ;
	MaxHeapSize = MAXSIZE;
	HeapSize=0;
}
 
template <typename type> Heap<type>::Heap(int IntArray[], int Count){
 
	int CurrentPosition;
	if (Count <= 0){
		cerr << "Cannot construct a heap with size 0 or less." << endl;
		exit(1);
	}	
 
	MaxHeapSize = Count;
	HeapSize = Count;
	HeapArrayPtr = IntArray;// a pointer assignment statement
	CurrentPosition = (HeapSize - 2) / 2;// Set CurrentPosition to the last index of a parent node:
 
	while (CurrentPosition >= 0){// Get heap condition for subtree rooted at index CurrentPosition:
		FilterDown(CurrentPosition);
		CurrentPosition--;
	}
}
 
//DELETE()
template <typename type> type Heap<type>::Delete(){
 
	int Temp;
	if (HeapSize == 0){
		cerr << "Cannot remove from an empty heap" << endl;
		exit(1);
	}
 
	Temp = HeapArrayPtr[0];   // Item at index 0 is the smallest
	HeapArrayPtr[0] = HeapArrayPtr[HeapSize - 1];// copy last one to root:
	HeapSize--;
	FilterDown(0);   // readjust to be a heap
	return Temp;
}
 
//FILTER DOWN()
template <typename type> void Heap<type>::FilterDown(int StartIndex){
 
   int CurrentPosition, ChildPosition, RightChildPosition, Target;
   CurrentPosition = StartIndex;
   Target = HeapArrayPtr[StartIndex];
   ChildPosition = LeftChild(CurrentPosition);
 
   while (ChildPosition < HeapSize){
      RightChildPosition = ChildPosition + 1;//  Set ChildPosition to index of smaller of right, left children:
 
      if ((RightChildPosition < HeapSize) && (HeapArrayPtr[RightChildPosition] <= HeapArrayPtr[ChildPosition]))
        ChildPosition = RightChildPosition;
 
      if (Target <= HeapArrayPtr[ChildPosition])
        break;  // Get out of loop, heap OK with Target at CurrentPosition
 
	  HeapArrayPtr[CurrentPosition] = HeapArrayPtr[ChildPosition];// Move value of the smaller child to the parent node:
      CurrentPosition = ChildPosition;// Move down the tree:
	  ChildPosition = LeftChild(CurrentPosition);
	}
	HeapArrayPtr[CurrentPosition] = Target;// Put Target into the correct location:
}
 
//FILTER UP()
template <typename type> void Heap<type>::FilterUp(int StartIndex){
 
   int CurrentPosition, ParentPosition;
   type Target;
   CurrentPosition = StartIndex;
   ParentPosition = Parent(CurrentPosition);
   Target = HeapArrayPtr[StartIndex];
 
   while (CurrentPosition != 0){
      if (HeapArrayPtr[ParentPosition] <= Target)
         break; // Get out of loop, heap OK with Target at CurrentPosition
 
	  HeapArrayPtr[CurrentPosition] = HeapArrayPtr[ParentPosition];// Move parent value to child:
      CurrentPosition = ParentPosition;// Move up in the tree:
      ParentPosition = Parent(CurrentPosition);
    }
	HeapArrayPtr[CurrentPosition] = Target;// Place Target at the position located for it:
}
 
//INSERT()
template <typename type> void Heap<type>::Insert(type Item){
 
   if (HeapSize == MaxHeapSize){
      cerr << "Cannot insert into a full heap" << endl;
      exit(1);
    }
 
   HeapArrayPtr[HeapSize] = Item;// At first, place item at the end of the heap:
   FilterUp(HeapSize);   // restore heap property
   HeapSize++;
}
 
//SORT()
template <typename type> void Heap<type>::SORT(type IntArray[], int MAX){
 
	type Smallest;
	int a;
	Heap (IntArray, MAX);  // constructor makes IntArray a heap
 
	for (a = MAX - 1; a >= 1; a--){
		Smallest = Delete();// Remove smallest item and place at index k
		IntArray[a] = Smallest;// At this point IntArray[0] contains the largest item by default
	}
 
	cout<<"print data in descending order"<<endl;
 
	for (int k = 0; k <MAX; k++){     
      cout << setw(10) << IntArray[k];
	}
 
   cout << endl;
} 
 
//FindMin()
 
template <typename type> type Heap<type>::FindMin(){
	type Temp;
 
	if (HeapSize == 0){
		cerr << "empty heap" << endl;
		exit(1);
	}
 
	return  Temp = HeapArrayPtr[0];   // Item at index 0 is the smallest
}
 
//FINDMax()
template <typename type> type Heap<type>::FindMax(){
 
	type temp1;
	temp1=HeapArrayPtr[0];
 
	if (HeapSize == 0){
		cerr << "empty heap" << endl;
		exit(1);
	}
 
	for(int i=1; i<MaxHeapSize; i++){
 
		if(temp1<HeapArrayPtr[i])
			temp1=HeapArrayPtr[i];
 
	}
    return temp1;
}
 
//Remove()
template <typename type> void Heap<type>::Remove(type item){
 
	for(int i=0; i<MaxHeapSize; i++){
      if(HeapArrayPtr[i]==item){
		HeapArrayPtr[i] = HeapArrayPtr[HeapSize - 1];
		//      HeapSize--;
	  }
	}
 
	Heap(HeapArrayPtr, MaxHeapSize-1);
}

#include "heap.h"
int main(){
	Heap<int> h(10);
	for(int i=1;i<=10;++i) h.Insert(i);
	cout<<h.IsEmpty();
	int max=h.FindMax();
	int min=h.FindMin();
	for(int i=1;i<=10;++i) cout<<h[i];
	h.Remove(20);
	int a[10],b=10;
	h.SORT(a,b);
	h.Delete();
	Heap<int> g(a,b);
	return 0;
}