介绍

最小堆的实现

介绍

最大堆和最小堆是二叉堆的两种形式。

最大堆：根结点的键值是所有堆结点键值中最大者。

最小堆：根结点的键值是所有堆结点键值中最小者。

而最大-最小堆集结了最大堆和最小堆的优点，这也是其名字的由来。

最大-最小堆是最大层和最小层交替出现的二叉树，即最大层结点的儿子属于最小层，最小层结点的儿子属于最大层。

以最大（小）层结点为根结点的子树保有最大（小）堆性质：根结点的键值为该子树结点键值中最大（小）项。

最小堆的实现

#include <iostream>

using namespace std;

template<class T>

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 RemoveMin(); //删除最小元素

T GetMin(); //取最小元素

bool IsEmpty() const;

bool IsFull() const;

void Clear();

};

template<class T>

MinHeap<T>::MinHeap(int n)

{

MaxSize=n;

heap=new T[MaxSize];

CurrentSize=0;

}

template<class T>

MinHeap<T>::~MinHeap()

{

delete []heap;

}

template<class T>

void MinHeap<T>::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<class T>

void MinHeap<T>::FilterDown(const int start,const int end) //自上往下调整，使关键字小的节点在上

{

int i=start,j=2*i+1;

T temp=heap[i];

while(j<=end)

{

if( (j<end) && (heap[j]>heap[j+1]) )

j++;

if(temp<=heap[j])

break;

else

{

heap[i]=heap[j];

i=j;

j=2*j+1;

}

}

heap[i]=temp;

}

template<class T>

bool MinHeap<T>::Insert(const T &x)

{

if(CurrentSize==MaxSize)

return false;

heap[CurrentSize]=x;

FilterUp(CurrentSize);

CurrentSize++;

return true;

}

template<class T>

T MinHeap<T>::RemoveMin( )

{

T x=heap[0];

heap[0]=heap[CurrentSize-1];

CurrentSize--;

FilterDown(0,CurrentSize-1); //调整新的根节点

return x;

}

template<class T>

T MinHeap<T>::GetMin()

{

return heap[0];

}

template<class T>

bool MinHeap<T>::IsEmpty() const

{

return CurrentSize==0;

}

template<class T>

bool MinHeap<T>::IsFull() const

{

return CurrentSize==MaxSize;

}

template<class T>

void MinHeap<T>::Clear()

{

CurrentSize=0;

}

//最小堆：根结点的键值是所有堆结点键值中最小者。

int main ()

{

int k,n=11,a[11]={0,5,2,4,9,7,3,1,10,8,6};

MinHeap<int> test(11);

for(k=0; k<n; k++)

test.Insert(a[k]);

cout<<test.IsFull()<<endl;

for(k=0;k<n;k++)

cout<<test.RemoveMin()<<ends;

cout<<endl;

return 0;

}