#include <iostream>
using namespace std;
class MinHeap
{
private:
  int *heapArray;
  int maxheapSize;
  int heapsize;

public:
//構造函數
  MinHeap(int);
//刪除堆
  void Destroyheap();
//清除堆
  void Clearheap();
//判斷堆是否為空
  bool IsHeapEmpty();
//判斷堆是否為滿
  bool IsHeapFull();
//返回堆的堆頂元素
  int GetTop();
//調整堆函數
  void FilterUp();
//調整堆函數
  void FilterDown();
//輸出函數
  void PrintArray(int a[],int n);
//插入函數
  void InsertHeap(int item);
//刪除函數
  int DeleteHeap();
};
MinHeap::MinHeap(int MaxSize)
{
	if(MaxSize<=0) 
	{
         cerr<<"初始化個數不能小于等于0！\n";
		 exit(1);
	}
    heapArray=(int *) new int[MaxSize];
    if(!heapArray)
	{
		cerr<<"內存分配錯誤！";
		exit(-1);
	}
	maxheapSize=heapsize;
    heapsize=0;
}

//刪除堆函數
void MinHeap::Destroyheap()
{
    delete [] heapArray;
}

//清除堆元素函數
void MinHeap::Clearheap()
{
	heapsize=0;
}

//判斷空函數
bool MinHeap::IsHeapEmpty()
{ 
	if(heapsize==0) 
	{
		return true;
	}
    else
	{
		return false;
	}
}

//判斷為滿函數
bool MinHeap::IsHeapFull()
{
	return heapsize==maxheapSize;
}

//返回堆頂元素函數
int MinHeap::GetTop()
{ 
    if(heapsize==0)
    {
		cerr<<"堆為空！不能獲取堆頂元素！\n";
		exit(1);
	}
    return heapArray[0];
}

//調整函數
void MinHeap::FilterUp()
{
	int c,p;
    int temp;
    c=heapsize-1;
    p=(c-1)/2;
    temp=heapArray[c];
    while(c!=0)
	{
		if(heapArray[p]<=temp)
			break;
        heapArray[c]=heapArray[p];
        c=p;
        p=(c-1)/2;
	}
    heapArray[c]=temp;
}

//調整函數
void MinHeap::FilterDown()
{
	int c,p;
    int temp;
    p=0;
    c=2*p+1;
    temp=heapArray[p];
    while(c<heapsize)
	{
		if(c+1<heapsize&&heapArray[c+1]<heapArray[c])
          c=c+1;
        if(temp<=heapArray[c]) 
			break;
         heapArray[p]=heapArray[c];
         p=c;
         c=2*p+1;
	}
    heapArray[p]=temp;
}

//插入堆元素函數
void MinHeap::InsertHeap(int item)
{
	if(heapsize==heapsize)
	{
		cerr<<"堆已滿，不能再進行插入！\n";
		exit(1);
	}
    heapArray[heapsize]=item;
    heapsize++;
    FilterUp();
}

//刪除堆元素函數
int MinHeap::DeleteHeap()
{
	int temp;
    if(heapsize==0)
	{
		cerr<<"堆已空！沒有可刪除的元素！\n";
		exit(1);
	}
    temp=heapArray[0];
   heapArray[0]=heapArray[heapsize-1];
   heapsize--;
   FilterDown();
   return(temp);
}


//輸入堆元素函數
void MinHeap::PrintArray(int a[],int n)
{
	for(int i=0;i<n;i++)
	{
      cout<<"   "<<a[i];
	}
    cout<<endl;
}

//主函數
void main()
{
	int num;
    cout<<"======構造堆=======：\n";
    cout<<"請輸入堆元素個數：";
    cin>>num;
    int b[100];
    int elem;
    MinHeap H(num);
    for(int i=0;i<num;i++)
	{
       cin>>elem;
       b[i]=elem;
	}
   cout<<"你所輸入的數組為：\n";
   H.PrintArray(b,num);
   for(i=0;i<num;i++)
   {
      H.InsertHeap(b[i]);
   }
   cout<<"當前堆的堆頂元素：\n";
   cout<<"   "<<H.GetTop()<<endl;
   cout<<"按最小堆排列后的元素：\n";
   H.PrintArray(b,num);
   cout<<"逐個刪除的H堆中元素：\n";
   while(!H.IsHeapEmpty())
   {
      cout<<"   "<<H.DeleteHeap();
   }
   cout<<endl;

}