最小堆
介绍最大堆和最小堆是二叉堆的两种形式。
最大堆：根结点的键值是所有堆结点键值中最大者。
最小堆：根结点的键值是所有堆结点键值中最小者。
而最大-最小堆集结了最大堆和最小堆的优点，这也是其名字的由来。
最大-最小堆是最大层和最小层交替出现的二叉树，即最大层结点的儿子属于最小层，最小层结点的儿子属于最大层。
以最大（小）层结点为根结点的子树保有最大（小）堆性质：根结点的键值为该子树结点键值中最大（小）项。
最小堆的实现一个自实现的优先队列 最小堆 #include
#include
#include
using namespace std;
template
class MinHeap
{
private:
T *heap;
int CurrentSize;
int MaxSize;
void FilterDown(const int start,const int end);
void FilterUp(int start);
public:
MinHeap(int n);
MinHeap();
~MinHeap(){delete []heap;}
bool Insert(const T &x);
T RemoveMin();
T GetMin();
bool IsEmpty() const{return CurrentSize==0;}
bool IsFull() const{return CurrentSize==MaxSize;}
void Clear(){CurrentSize=0;}
};
template
MinHeap::MinHeap()
{
MaxSize=1000;
heap=new T[MaxSize];
CurrentSize=0;
}
template
MinHeap::MinHeap(int n)
{
MaxSize=n;
heap=new T[MaxSize];
CurrentSize=0;
}
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
void MinHeap::FilterUp(int start)
{
int j=start,i=(j-1)/2;
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
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];
}
int main ()
{
MinHeap test(8);
int k;
bool tem;
for(k=1;k<=10;k++)
{
tem=test.Insert(10-k);
}
tem=test.IsEmpty();
tem=test.IsFull();
for(k=1;k<=5;k++)
test.RemoveMin();
return 0;
}