最小堆的优先队列实现。     在建立最小堆或最大堆时。最主要的就是理解。SiftDown和SiftUp算法的实现问题。其实我觉得自己在画一棵树。先比较左右再比较父点之间。是最大堆往上。最小堆往下。就很能理解了， 下面程序是最小堆。#include <iostream>using namespace std; template<class Elem>class MinHeap{private: Elem* heapArray; int CurrentSize; int MaxSize;public: MinHeap(const int n); virtual~ MinHeap() {  delete []heapArray; } void BuildHeap(); bool isLeaf(int pos) const; int leftChild(int pos) const; int rightChild(int pos) const; //return parent position int parent(int pos) const; //删除给定下标的元素。 bool Remove(int pos,Elem& node); void SiftDown(int left); void SiftUp(int position); bool Insert(const Elem& newNode); Elem& RemoveMin(); bool print() const;};template<class Elem>MinHeap<Elem>::MinHeap(const int n){ if(n<=0)  return ; CurrentSize=0; MaxSize=n; heapArray=new Elem[MaxSize]; BuildHeap();} template<class Elem>void MinHeap<Elem>::BuildHeap(){ for(int i=CurrentSize/2-1;i>=0;i--)  SiftDown(i);} template<class Elem>bool MinHeap<Elem>::isLeaf(int pos) const{ return (pos>=CurrentSize/2) && (pos<CurrentSize);} template<class Elem>int MinHeap<Elem>::leftChild(int pos) const{ return 2*pos+1;} template<class Elem>int MinHeap<Elem>::rightChild(int pos) const{ return 2*pos+2;} template<class Elem>int MinHeap<Elem>::parent(int pos) const{ return (pos-1)/2;}//向下筛选。template<class Elem>void MinHeap<Elem>::SiftDown(int left){ int i=left;          。                  //标记父结点 int j=2*i+1; Elem temp=heapArray[i];  while(j<CurrentSize) {  if((j<CurrentSize-1) && (heapArray[j]>heapArray[i]))     j++;                          //指向右子结点     if(temp>heapArray[j])   {    heapArray[i]=heapArray[j];    i=j;    j=2*j+1;   }     else     break;  } heapArray[i]=temp;}//向上筛选template<class Elem>void MinHeap<Elem>::SiftUp(int position){ int temppos=position; Elem temp=heapArray[temppos]; while((temppos>0) && (heapArray[parent(temppos)]>temp)) {  heapArray[temppos]=heapArray[parent(temppos)];  temppos=parent(temppos); } heapArray[temppos]=temp;} template<class Elem>bool MinHeap<Elem>::Insert(const Elem& newNode){ if(CurrentSize==MaxSize)  return false; heapArray[CurrentSize]=newNode; SiftUp(CurrentSize); CurrentSize++; return true;} template<class Elem>Elem& MinHeap<Elem>::RemoveMin(){ if(CurrentSize==0) {    cout<<"Can't Delete "; } else {  Elem temp=heapArray[0];  heapArray[0]=heapArray[CurrentSize-1];  CurrentSize--;  if(CurrentSize>1)   SiftDown(0);  return temp; }}   template<class Elem>bool MinHeap<Elem>::Remove(int pos,Elem& node){ if((pos<0) || (pos>CurrentSize))  return false; Elem temp=heapArray[pos]; heapArray[pos]=heapArray[--CurrentSize]; SiftUp(pos); SiftDown(pos); node=temp; return true;} template<class Elem>bool MinHeap<Elem>::print() const{  if(CurrentSize<0)   return false;  for(int i=0;i<CurrentSize;i++)   cout<<heapArray[i]<<" ";  return true;} int main(){ MinHeap<char> A(20); char item; int pos; cout<<"Enter 20 number:"<<endl; for(int i=0;i<20;i++) {  cout<<"the"<<i<<"NO: ";  cin>>item;  A.Insert(item); } cout<<"\nPrint all the number: "; A.print(); A.RemoveMin(); cout<<"\nAfter delete the Min number:"; A.print(); cout<<"\nEnter the positon you want:"; cin>>pos; A.Remove(pos,item); cout<<"\nThe data is:"<<item<<endl; return 0;} //程序示例：/*Enter 20 number:the0NO: athe1NO: qthe2NO: zthe3NO: wthe4NO: sthe5NO: xthe6NO: ethe7NO: dthe8NO: cthe9NO: rthe10NO: fthe11NO: vthe12NO: tthe13NO: gthe14NO: bthe15NO: ythe16NO: hthe17NO: nthe18NO: uthe19NO: j Print all the number: a c b d f t e h n j r z v x g y w q u sAfter delete the Min number:c f b d r t e h n j s z v x g y w q uEnter the positon you want:13 The data is:x*/   

评论