最小堆，是一种经过排序的
完全二叉树，其中任一非终端节点的数据值均不大于其左子结点和右子结点的值。
数据介绍
堆是一种经过排序的
完全二叉树，其中任一非终端节点的数据值均不大于（或不小于）其左子节点和右子节点的值。
最大堆：根结点的键值是所有堆结点键值中最大者。
最小堆：根结点的键值是所有堆结点键值中最小者。
而最大-最小堆集结了最大堆和最小堆的优点，这也是其名字的由来。
最大-最小堆是最大层和最小层交替出现的
二叉树，即最大层结点的儿子属于最小层，最小层结点的儿子属于最大层。
以最大（小）层结点为根结点的
子树保有最大（小）堆性质：根结点的键值为该子树结点键值中最大（小）项。
最小堆的实现
#include
template
class MinHeap{
private:
T *heap; //元素数组，0号位置也储存元素
int CurrentSize; //目前元素个数
int MaxSize; //可容纳的最多元素个数
void FilterDown(const int start,const int end); //自上往下调整，使关键字小的节点在上
void FilterUp(int start); //自下往上调整
public:
MinHeap(int n=1000);
~MinHeap();
bool Insert(const T &x); //插入元素
T GetMin(); //取最小元素
bool IsFull() const;
void Clear();
};
template
MinHeap::MinHeap(int n){
MaxSize=n;
heap=new T[MaxSize];
CurrentSize=0;
}
template
MinHeap::~MinHeap(){
delete []heap;
}
template
void MinHeap::
FilterUp(int start){//自下往上调整
int j=start,i=(j-1)/2; //i指向j的双亲节点
T temp=heap[j];
while(j>0){
if(heap[i]<=temp)
break;
else{
heap[j]=heap[i];
j=i;
i=(i-1)/2;
}
}
heap[j]=temp;
}
template
void MinHeap::FilterDown(const int start,const int end）{//自上往下调整，使关键字小的节点在
int i=start,j=2*i+1;
T temp=heap[i];
while(j<=end){
if( (jheap[j+1]) )
j++;
if(temp<=heap[j])
break;
else{
heap[i]=heap[j];
i=j;
j=2*j+1;
}
}
heap[i]=temp;
}
template
bool MinHeap::Insert(const T &x){
if(CurrentSize==MaxSize)
return false;
heap[CurrentSize]=x;
FilterUp(CurrentSize);
CurrentSize++;
return true;
}
template
T MinHeap::RemoveMin( ){
T x=heap[0];
heap[0]=heap[CurrentSize-1];
CurrentSize--;
FilterDown(0,CurrentSize-1); //调整新的
根节点 return x;
}
template
T MinHeap::GetMin(){
return heap[0];
}
template
bool MinHeap::IsEmpty() const{
return CurrentSize==0;
}
template
bool MinHeap::IsFull() const{
return CurrentSize==MaxSize;
}
template
void MinHeap::Clear(){
CurrentSize=0;
}
//最小堆：
根结点的
键值是所有堆结点键值中最小者。
int main (){
int k,n=11,a[11]={0,5,2,4,9,7,3,1,10,8,6};
MinHeap test(11);
for(k=0; k
test.Insert(a[k]);
cout<
for(k=0;k
cout<
cout<
return 0;
}
如果有一个关键字的集合K={k0,k1,k2, ..., kn-1}, 把所有元素按
完全二叉树的
顺序存储方式存放在一个
一维数组中，并且满足ki <= k2i+1 且 ki <= k2i+2 (i = 0, 1, ..., (n-2)/2 向上取整)则称这个集合为小根堆。