heap.cpp

程序用VC编写

#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;

}