VC++2012程式設計演練資料結構《27》最小堆二叉樹

最大堆和最小堆是二叉堆的兩種形式。

　　最大堆：根結點的鍵值是所有堆結點鍵值中最大者。

　　最小堆：根結點的鍵值是所有堆結點鍵值中最小者。

　　而最大-最小堆集結了最大堆和最小堆的優點，這也是其名字的由來。

　　最大-最小堆是最大層和最小層交替出現的二叉樹，即最大層結點的兒子屬于最小層，最小層結點的兒子屬于最大層。

　　以最大（小）層結點為根結點的子樹保有最大（小）堆性質：根結點的鍵值為該子樹結點鍵值中最大（小）項。

打開ＩＤＥ

我們來建立一個工程

類聲明如下

#if !defined(AFX_MINHEAP_H__5F262696_5BC2_4DC3_BD5A_54F6DEAD15DA__INCLUDED_)
#define AFX_MINHEAP_H__5F262696_5BC2_4DC3_BD5A_54F6DEAD15DA__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include "stdafx.h"


//最小堆的類定義minheap.h
#define HeapSIZE 10
#define MaxHeapSize 100

class minheap
{private:
ElemType *heapArray;
int maxheapSize;
int heapsize;
public:
	//構造一個空堆S
	minheap(int);
	//堆存在則堆被銷毀
	void Destroyheap();
	//堆存在則清為空堆
	void Clearheap();
	//堆空則傳回true,否則false
	bool heapEmpty();
	//堆滿則傳回true,否則false
	bool heapFull();
	// 堆存在則傳回堆的元素個數,即堆的長度
	int heapLength();
	//堆存在且非空則傳回堆的堆頂元素
	ElemType GetTop();
	// 插入後的堆調整,使之符合最小堆的定義
	void FilterUp();
	//删除後的堆調整,使之符合最小堆的定義
	void FilterDown();
	//堆插入
	void heapInsert(ElemType item);
	//堆删除
	ElemType heapDelete();
};

#endif // !defined(AFX_MINHEAP_H__5F262696_5BC2_4DC3_BD5A_54F6DEAD15DA__INCLUDED_)
           

類實作如下

#include "stdafx.h"
#include "minheap.h"

//最小堆的實作minheap.cpp
#include "minheap.h"
minheap::minheap(int MaxSize)
{if(MaxSize<=0) {
  cerr<<"參數MaxSize非法!\n";exit(1);}
 heapArray=(ElemType *) new ElemType[MaxSize];
 if(!heapArray) exit(-1);
 maxheapSize=HeapSIZE;
 heapsize=0;
}
void minheap::Destroyheap()
{free(heapArray);}

void minheap::Clearheap()
{heapsize=0;}

bool minheap::heapEmpty()
{ if(heapsize==0) return true;
else return false;
}
bool minheap::heapFull()
{return heapsize==maxheapSize;}
int minheap::heapLength()
{ return heapsize;}
ElemType minheap::GetTop()
{ if(heapsize==0)
{cerr<<"堆已空!\n";exit(1);}
return heapArray[0];
}
void minheap::FilterUp()
{int c,p;
ElemType 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;
ElemType 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::heapInsert(ElemType item)
{if(heapsize==HeapSIZE)
{cerr<<"堆已滿!\n";exit(1);}
heapArray[heapsize]=item;
heapsize++;
FilterUp();
}
ElemType minheap::heapDelete()
{ElemType temp;
if(heapsize==0)
{cerr<<"堆已空!\n";exit(1);}
temp=heapArray[0];
heapArray[0]=heapArray[heapsize-1];
heapsize--;
FilterDown();
return(temp);}
           

類調用如下

#include "stdafx.h"

#include "minheap.h"
void PrintArray(int a[],int n)
{for(int i=0;i<n;i++)
  cout<<setw(3)<<a[i];
 cout<<endl;
}
void main()
{cout<<"運作結果:\n";
ElemType b[10];
srand(350);
for(int i=0;i<10;i++)
b[i]=rand()%100;
cout<<"輸出數組b:\n";
PrintArray(b,10);
minheap H(10),H1(10);
for(int i=0;i<10;i++)
H.heapInsert(b[i]);
cout<<"輸出目前堆H的堆頂元素:\n";
cout<<setw(3)<<H.GetTop()<<endl;
cout<<"輸出插入後數組b:\n";
PrintArray(b,10);
cout<<"輸出逐個删除的H堆中元素:\n";
while(!H.heapEmpty())
cout<<setw(3)<<H.heapDelete();
cout<<endl;
for(int i=0;i<10;i++)
H1.heapInsert(rand()%100);
cout<<"輸出目前堆H1的堆頂元素:\n";
cout<<setw(3)<<H1.GetTop()<<endl;
cout<<"輸出逐個删除的H1堆中元素:\n";
while(!H1.heapEmpty())
cout<<setw(3)<<H1.heapDelete();
cout<<endl;
H.Destroyheap();H1.Destroyheap();
 getch();}           

效果如下