数据结构堆的有关操作.doc

#include#includetemplateclass minheapprivate:T *heaparray; /存放堆数据的数组int currentsize; /当前堆中的元素数目int maxsize; /最大元素数目void swap(int pos_x,int pos_y); /交换位置x和y的元素void buildheap(); /建堆public:minheap(const int n); /构造函数，参数n为堆的最大元素数目virtual minheap(); /析构函数bool isempty(); /判断堆是否为空bool isleaf(int pos)const; /判断是否为叶结点int leftchild(int pos)const; /返回左孩子的位置int rightchild(int pos)const; /返回右孩子的位置int parent(int pos)const; /返回父接点的位置bool remove(int pos,T & node); /删除给定下标的元素bool insert(const T & newnode);/向堆中插入新元素newnodeT & removemin();/从堆顶删除最小值void siftup(int position);/从position开始向上调整void siftdown(int left);/从left开始向下筛选void print();templateminheap:minheap(const int n)if(n=0)return;currentsize=0;maxsize=n;heaparray=new Tmaxsize;int a100;for(int i=0;iai;heaparraycurrentsize=ai;currentsize+;buildheap();template minheap:minheap()deleteheaparray;templatebool minheap:isleaf(int pos)constif(pos=currentsize/2)&(poscurrentsize)cout是叶结点endl;return true;elsecout不是叶结点endl;return false;templatevoid minheap:buildheap()for(int i=currentsize/2-1;i=0;i-)siftdown(i);templateint minheap:leftchild(int pos)constreturn 2*pos+1;templateint minheap:rightchild(int pos)constreturn 2*pos+2;templateint minheap:parent(int pos)constreturn(pos-1)/2;templatebool minheap:insert(const T & newnode)if(currentsize=maxsize)return false;heaparraycurrentsize=newnode;siftup(currentsize);currentsize+;return true;templateT & minheap:removemin()if(currentsize=0)coutcant delete;exit(1);elsecoutheaparray01)siftdown(0);return heaparraycurrentsize;templatebool minheap:remove(int pos,T & node)if(pos=currentsize)return false;node=heaparraypos;heaparraypos=heaparray-currentsize;if(heaparrayparent(pos)heaparraypos)siftup(pos);else siftdown(pos);return true;templatevoid minheap:siftup(int position)int temppos=position;T temp=heaparraytemppos;while(temppos0)&(heaparrayparent(temppos)temp)heaparraytemppos=heaparrayparent(temppos);temppos=parent(temppos);heaparraytemppos=temp;templatevoid minheap:siftdown(int left)int i=left;int j=leftchild(i);T temp=heaparrayi;while(jcurrentsize)if(jheaparrayj+1)j+;if(tempheaparrayj)heaparrayi=heaparrayj;i=j;j=leftchild(j);else break;heaparrayi=temp;templatevoid minheap:swap(int pos_x,int pos_y)T p;p=heaparraypos_x;heaparraypos_x=heaparraypos_y;heaparraypos_y=p;templatevoid minheap: