用于堆排序的最大堆类模板的定义：
#ifndef MAXHEAP_H
#define MAXHEAP_H
#define DefaultSize 50
#include<iostream.h>
#include<stdlib.h>
////////////////////////////////////////////////////
//数据表元素Element<T,E>类模板的实现
//T是数据元素的关键码类型,E是元素的数据域的类型
////////////////////////////////////////////////////
template<class T,class E>
class Element
{
public:
T key;
//数据元素的关键码
E data;
//数据元素的数据域
Element()
//默认构造函数
{key=0;data=0;};
Element(T k,E d)
//构造函数
{key=k;data=d;};
T getkey()
//获取关键码
{return key;};
T getdata()
//获取关键码
{return data;};
//成员重载赋值运算符
Element<T,E>& operator=(Element<T,E>& R)
{key=R.key;data=R.data;return *this;}
//成员重载下列的关系运算符
bool operator==(Element<T,E>& R)
{return key==R.key;};
bool operator<=(Element<T,E>& R)
{return key<=R.key;};
bool operator>=(Element<T,E>& R)
{return key>=R.key;};
bool operator<(Element<T,E>& R)
{return key<R.key;};
bool operator>(Element<T,E>& R)
{return key>R.key;};
bool operator!=(Element<T,E>& R)
{return key!=R.key;};
//友元重载<<输出运算符
friend ostream& operator<<(ostream& os,Element<T,E>& R);
};
///////////////////////////////////Element类定义结束
////////////////////////////////////////////////////
//友元重载<<输出运算符
////////////////////////////////////////////////////
template<class T,class E>
ostream& operator<<(ostream& os,Element<T,E>& R)
{
os<<R.key<<":"<<R.data;
return os;
};
//////////////////////////////////////<<友元重载结束
////////////////////////////////////////////////////
//MaxHeap<T,E>最大堆的定义
//即根结点的元素大于它的左右子结点
////////////////////////////////////////////////////
template<class T,class E>
class MaxHeap
{
private:
Element<T,E>* heap;
//存放最大堆中的元素
int currentSize;
//当前堆中元素的个数
int maxHeapSize;
//堆的最大容量
void siftDown(int start,int m);//从start到m进行自顶向下的调整
void siftUp(int start);
//从start到0自底向上调整
void Swap(int i,int j)
//交换i和j对应的元素
{
Element<T,E> temp;
temp=heap[i];
heap[i]=heap[j];
heap[j]=temp;
};
public:
MaxHeap(int sz=DefaultSize);
//默认构造函数,建立一个空堆
MaxHeap(Element<T,E> arr[],
//构造函数,通过数组来初始化堆
int n);
~MaxHeap(){delete [] heap;}
//析构函数,释放堆的内存
bool Insert(Element<T,E>& x);
//把元素x插入到最大堆中
bool Remove(Element<T,E>& x);
//删除堆顶的最大的元素
bool IsEmpty()const
//判空
{return currentSize==0;};
bool IsFull()const
//判满
{return currentSize==maxHeapSize};
void HeapSort();
//利用当前的堆进行排序
};
///////////////////////////////////MaxHeap类模板结束
////////////////////////////////////////////////////
//默认构造函数
构造一个空的最大堆
////////////////////////////////////////////////////
template<class T,class E>
MaxHeap<T,E>::MaxHeap(int sz)
{
maxHeapSize=sz;
heap=new Element<T,E>[maxHeapSize];
if(heap==NULL)
{
cout<<"内存分配失败!"<<endl;
exit(1);
}
currentSize=0;
};
////////////////////////////////////默认构造函数结束
////////////////////////////////////////////////////
//带参数的构造函数
//通过数组来初始化当前的最大堆,n是元素的个数
////////////////////////////////////////////////////
template<class T,class E>
MaxHeap<T,E>::MaxHeap(Element<T,E> arr[],int n)
{
/*初始化工作*/
maxHeapSize=2*n;
//最大元素个数是当前个数的两倍
heap=new Element<T,E>[maxHeapSize];
currentSize=n;
//当前元素的个数
for(int i=0;i<n;i++)
//对堆数组进行赋值
heap[i]=arr[i];
/*通过siftDown()进行堆序调整*/
int currentPos=(currentSize-2)/2;//得到当前的最后一个分支结点的位置
for(;currentPos>=0;currentPos--)
siftDown(currentPos,currentSize-1);
};
////////////////////////////////带参数的构造函数结束
////////////////////////////////////////////////////
//siftDown()私有成员函数
//进行一次调整堆,即从当前结点start开始逐个向下调整
//一直到m为止结束,因为下沉调整的前提是当前结点的
//左右子树已经构成了一个堆,所以该函数的使用应该从
//最后一个分支结点往前进行调整进行
////////////////////////////////////////////////////
template<class T,class E>
void MaxHeap<T,E>::siftDown(int start,int end)
{
int p=start;
//当前的比较结点
int q=2*p+1;
//指向当前结点的左子女
while(q<=end)
{
if(heap[p]<heap[q] || heap[p]<heap[q+1])
{
if(q+1<=end && heap[q]<heap[q+1])
q=q+1;
Swap(p,q);
p=q;
q=2*p+1;
}
else
break;
};
};
//////////////////////////////////siftDown()函数结束
////////////////////////////////////////////////////
//siftUp()公有成员函数
//从当前结点start开始向根结点0进行一次上浮调整
//一般认为start是从叶子结点开始
////////////////////////////////////////////////////
template<class T,class E>
void MaxHeap<T,E>::siftUp(int start)
{
int p=start;
//游标指针
int q;
//当前结点p的父结点指针
while(p>0)
//循环向上比较
{
q=int((p-1)/2);
//父结点指针
if(heap[p]>heap[q])
//如果子结点大于父结点
Swap(p,q);
//把大的元素上浮调整
p=q;
//不管怎样继续向上比较
};
};
////////////////////////////siftUp()私有成员函数结束
////////////////////////////////////////////////////
//Insert()公有成员函数
//在堆中插入一个元素并重新调整堆序
//只需要从最后一个结点向根结点进行一次siftUp()调整
////////////////////////////////////////////////////
template<class T,class E>
bool MaxHeap<T,E>::Insert(Element<T,E>& x)
{
//如果堆已经满了
if(currentSize==maxHeapSize)
{
cout<<"当前的堆已经满了,无法插入!"<<endl;
return false;
};
//把新元素插入到堆尾
heap[currentSize]=x;
//个数加一
currentSize++;
//对刚插入的结点进行一次向上调整
siftUp(currentSize-1);
//插入成功
return true;
};
////////////////////////////Insert()公有成员函数结束
////////////////////////////////////////////////////
//Remove()公有成员函数
//删除堆的顶部的最大的元素,即可以将用heap数组中的
//最后一个元素填补到堆的顶部,并对该顶部结点作一次
//下沉调整,因为左右子树都已经是堆了
////////////////////////////////////////////////////
template<class T,class E>
bool MaxHeap<T,E>::Remove(Element<T,E>& x)
{
if(currentSize==0)
//如果当前堆是空的
return false;
x=heap[0];
heap[0]=heap[currentSize-1]; //用最后一个元素填充堆顶
currentSize--;
siftDown(0,currentSize-1);
//对刚替换的堆顶作一次下沉调整
return true;
};
////////////////////////////////////Remove()函数结束
