VC++2012编程演练数据结构《26》最大堆二叉树

大灰狼 · 发表于 2014-8-19 08:56:37

最大堆是二叉堆的两种形式之一。根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆,又称最大堆.

　　注意： ①堆中任一子树亦是堆。 ②以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆

最大堆和最小堆是二叉堆的两种形式。
　　最大堆：根结点的键值是所有堆结点键值中最大者。
　　最小堆：根结点的键值是所有堆结点键值中最小者。
　　而最大-最小堆集结了最大堆和最小堆的优点，这也是其名字的由来。
　　最大-最小堆是最大层和最小层交替出现的二叉树，即最大层结点的儿子属于最小层，最小层结点的儿子属于最大层。
　　以最大（小）层结点为根结点的子树保有最大（小）堆性质：根结点的键值为该子树结点键值中最大（小）项。

打开ＩＤＥ

我们创建一个工程

最大堆类声明如下

[cpp] view plaincopy

#if !defined(AFX_MAXHEAP_H__AA93A2ED_DA7B_4257_A6D1_024A26984D71__INCLUDED_)
#define AFX_MAXHEAP_H__AA93A2ED_DA7B_4257_A6D1_024A26984D71__INCLUDED_
#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
//最大堆的类定义maxheap.h
#define HeapSIZE 15
#define MaxHeapSize 100
#include "stdafx.h"
class maxheap
{private:
ElemType *heapArray;
int maxheapSize;
int heapsize;
public:
//构造一个空堆S
maxheap(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_MAXHEAP_H__AA93A2ED_DA7B_4257_A6D1_024A26984D71__INCLUDED_)

最大堆类实现如下

[cpp] view plaincopy

#include "stdafx.h"
#include "maxheap.h"
//最大堆的实现maxheap.cpp
#include "maxheap.h"
maxheap::maxheap(int MaxSize)
{if(MaxSize<=0) {
cerr<<"参数MaxSize非法!\n";exit(1);}
heapArray=(ElemType *) new ElemType[MaxSize];
if(!heapArray) exit(-1);
maxheapSize=HeapSIZE;
heapsize=0;
}
void maxheap::Destroyheap()
{free(heapArray);}
void maxheap::Clearheap()
{heapsize=0;}
bool maxheap::heapEmpty()
{ if(heapsize==0) return true;
else return false;
}
bool maxheap::heapFull()
{return heapsize==maxheapSize;}
int maxheap::heapLength()
{ return heapsize;}
ElemType maxheap::GetTop()
{ if(heapsize==0)
{cerr<<"堆已空!\n";exit(1);}
return heapArray[0];
}
void maxheap::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 maxheap::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 maxheap::heapInsert(ElemType item)
{if(heapsize==HeapSIZE)
{cerr<<"堆已满!\n";exit(1);}
heapArray[heapsize]=item;
heapsize++;
FilterUp();
}
ElemType maxheap::heapDelete()
{ElemType temp;
if(heapsize==0)
{cerr<<"堆已空!\n";exit(1);}
temp=heapArray[0];
heapArray[0]=heapArray[heapsize-1];
heapsize--;
FilterDown();
return(temp);
}

类调用如下

[cpp] view plaincopy

#include "stdafx.h"
#include "maxheap.h"
void PrintArray(int a[],int n)
{for(int i=0;i<n;i++)
cout<<setw(3)<<a;
cout<<endl;
}
void main()
{cout<<"maxheapm.cpp运行结果:\n";
ElemType b[HeapSIZE];
srand(350);
for(int i=0;i<HeapSIZE;i++)
b=rand()%100;
cout<<"输出数组b:\n";
PrintArray(b,HeapSIZE);
maxheap H(HeapSIZE),H1(HeapSIZE);
for(int i=0;i<HeapSIZE;i++)
H.heapInsert(b);
cout<<"输出当前堆H的堆顶元素:\n";
cout<<setw(3)<<H.GetTop()<<endl;
cout<<"输出插入后数组b:\n";
PrintArray(b,HeapSIZE);
cout<<"输出逐个删除的H堆中元素:\n";
while(!H.heapEmpty())
cout<<setw(3)<<H.heapDelete();
cout<<endl;
for(int i=0;i<HeapSIZE;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();
}

效果如下

		自动登录	找回密码
密码			立即注册

[图文教程] VC++2012编程演练数据结构《26》最大堆二叉树