这是一个用C++编写的代码,实现了最小堆和最小左偏树在插入删除元素性能方面进行比较.zip

#include<iostream.h> #include<stdlib.h> #include<time.h> int m=100000;//number of sequence const long r[7]={100,500,1000,2000,3000,4000,5000}; enum Boolean{FALSE,TRUE}; class MinHeap { public: Boolean HeapIsFull(); Boolean HeapIsEmpty(); void HeapInsert(const int &x); int*HeapDelete(int &x); MinHeap(int sz=32000) { int MaxSize=32000; cs=0; heap=new int[MaxSize+1];//heap[0] is not used } private: int*heap; int cs;//current size of heap int Maxsize; }; Boolean MinHeap::HeapIsFull() { if(cs==32000) return TRUE; else return FALSE; } Boolean MinHeap::HeapIsEmpty() { if(cs==0) return TRUE; else return FALSE; } void MinHeap::HeapInsert(const int &x) { if(cs==32000) {HeapIsFull();return;} cs++; for(int i=cs;1;) { if(i==1) break;//at root if(x>=heap[i/2]) break;//unneed to adjust heap[i]=heap[i/2]; i/=2; } heap[i]=x; } int* MinHeap::HeapDelete(int &x) { if(!cs) {HeapIsEmpty();return 0;} x=heap[1]; int k=heap[cs]; cs--; for(int i=1,j=2;j<=cs;) { if(j<cs) if(heap[j]>heap[j+1]) j++; //j points to the smaller child if(k<=heap[j]) break; heap[i]=heap[j];//move child up i=j; j*=2;//move i and j down } heap[i]=k; return &x; } class LeftistNode { friend class MinLeftistTree; public: LeftistNode(int d=0,LeftistNode*l=0,LeftistNode*r=0) { data=d; LeftChild=l; RightChild=r; } private: int data; LeftistNode*LeftChild; LeftistNode*RightChild; int shortest;//最短路径的值 }; class MinLeftistTree { public: MinLeftistTree(LeftistNode*root=0){}; Boolean TreeIsEmpty(); int*TreeDeleteMin(int &); void TreeMinCombine(LeftistNode*); LeftistNode *TreeMinUnion(LeftistNode*,LeftistNode*); LeftistNode *root; }; Boolean MinLeftistTree::TreeIsEmpty() { if(!root) return TRUE; else return FALSE; } void MinLeftistTree::TreeMinCombine(LeftistNode*b) { if(!root) root=b; else if(b) root=TreeMinUnion(root,b); } LeftistNode* MinLeftistTree::TreeMinUnion(LeftistNode*a,LeftistNode*b) //combine two nonempty min leftist trees { //set a to be min leftist tree with smaller root if((a->data)>(b->data)) {LeftistNode*t=a;a=b;b=t;} //creat binary tree such that the smallest key in each subtree is in the root if(!a->RightChild) a->RightChild=b; else a->RightChild=TreeMinUnion(a->RightChild,b); //leftist tree property if(!a->LeftChild) { //interchange subtrees a->LeftChild=a->RightChild; a->RightChild=0; } else if((a->LeftChild->shortest)<(a->RightChild->shortest)) { //interchange subtrees LeftistNode*t=a->LeftChild; a->LeftChild=a->RightChild; a->RightChild=t; } //set shortest data number if(!a->RightChild) a->shortest=1; else a->shortest=a->RightChild->shortest+1; return a; } int* MinLeftistTree::TreeDeleteMin(int &x) { if(!root) return 0; x=root->data; if(!root->RightChild) root=root->LeftChild; else root=TreeMinUnion(root->LeftChild,root->RightChild); return &x; } void tryheap() { srand((unsigned)time(NULL)); clock_t hstart,hend; int min; for(int n=0;n<7;n++) { MinHeap h; for (int i=1;i<r[n]+1;i++) h.HeapInsert(rand()%5000); hstart=clock(); for(int j=0;j<m;j++) { if((rand()%2)==0) { if(h.HeapIsEmpty()); else h.HeapDelete(min); } else { if(h.HeapIsFull()); else { int temp=rand()%5000; h.HeapInsert(temp); } } } hend=clock(); cout<<"n="<<r[n]<<" "<<"average time (min heap) is:"<<" " <<(hend-hstart)/(double)m<<endl; } cout<<endl; } void trytree() { srand((unsigned)time(NULL)); long start,end; for(int p=0;p<7;p++) { int min; MinLeftistTree z; LeftistNode tt(rand()%5000); z.root=&tt; for(int t=1;t<r[p];t++) { int min=rand()%5000; LeftistNode*element=new LeftistNode(min);//初始化liftisttree; z.TreeMinCombine(element); } start=clock(); for(int j=0;j<m;j++) { if((rand()%2)==0)//0代表删除元素 { if(z.TreeIsEmpty()) ; else z.TreeDeleteMin(min); } else //1代表插入元素 { int pmet=rand()%5000; LeftistNode*temp=new LeftistNode(pmet); z.TreeMinCombine(temp); } } end=clock(); cout<<"n="<<r[p]<<" "<<"average time (leftist tree) is:"<<" " <<(end-start)/(double)m<<endl; } } void main() { tryheap(); trytree(); }