編寫(xiě)優(yōu)先隊(duì)列數(shù)據(jù)(priority-queue)

T*array; intlength; intMaxSize;}Array;//定義一個(gè)數(shù)組，用來(lái)存放第一次錄入的數(shù)據(jù)。對(duì)應(yīng)有兩個(gè)函數(shù)操作usingnamespacestd;template<classT>//定義一種格式，當(dāng)T改變時(shí)，class類型改變,采用class才完成，用最大堆來(lái)存取classMaxHeap{public: MaxHeap(intMaxSize);intSize(){returnCurrentSize;}//求當(dāng)前堆的元素大小TMax(){if(CurrentSize==0)throwOutOfBounds();returnheap[1];}//求最大的元素 }}MaxHeap<T>&Insert(Tx);//插入MaxHeap<T>&DeleteMax(T&x);//刪除voidInitialize(Ta[],intsize);//初始化voidheapAdjust();//調(diào)整private:intCurrentSize,MaxSize;//當(dāng)前長(zhǎng)度和最大長(zhǎng)度T*heap;//元素?cái)?shù)組，用堆來(lái)存取};template<classT>MaxHeap<T>::MaxHeap(intMaxHeapSize){//構(gòu)造函數(shù)MaxSize=MaxHeapSize;heap=newT[MaxSize+1];CurrentSize=0;}voidMaxHeap<T>::heapAdjust()//調(diào)整{for(inti=CurrentSize/2;i>=1;i--){Ty=heap[i];//子樹(shù)的根//尋找放置y的位置intc=2*i;//c的父節(jié)點(diǎn)是y的目標(biāo)位置while(c<=CurrentSize){//heap[c]應(yīng)是較大的同胞節(jié)點(diǎn)if(c<CurrentSize&&heap[c]<heap[c+1])c++;//能把y放入heap[c/2]嗎?if(y>=heap[c])break;//能//不能heap[c/2]=heap[c];//將孩子上移c*=2;//下移一層{//把x插入到最大堆中if(CurrentSize==MaxSize)throwNoMem();//沒(méi)有足夠空間//為x尋找應(yīng)插入位置//i從新的葉節(jié)點(diǎn)開(kāi)始，并沿著樹(shù)上升inti=++CurrentSize;while(i!=1&&x>heap[i/2]){//不能夠把x放入heap[i]heap[i]=heap[i/2];//將元素下移i/=2;//移向父節(jié)點(diǎn)}heap[i]=x;return*this;}template<classT>x=heap[1];//最大元素//重構(gòu)堆Ty=heap[CurrentSize--];//最后一個(gè)元素//從根開(kāi)始，為y尋找合適的位置inti=1,//堆的當(dāng)前節(jié)點(diǎn)ci=2;//i的孩子while(ci<=CurrentSize){//heap[ci]應(yīng)是i的較大的孩子if(ci<CurrentSize&&heap[ci]<heap[ci+1])ci++;//能把y放入heap[i]嗎?if(y>=heap[ci])break;//能//不能heap[i]=heap[ci];//i=ci;//下移一層ci*=2; A.array=(T*)malloc(MAX*sizeof(T)); A.length=0; A.MaxSize=MAX;}voidGetArrayKey(Array&A)//輸入元素?cái)?shù)組的值{ cout<<"請(qǐng)輸入您數(shù)組集合的大小個(gè)數(shù)"<<endl; intn; cin>>n; intkey; cout<<"請(qǐng)輸入數(shù)據(jù)"<<endl; for(inti=1;i<=n;i++) { cin>>key; if(A.length>=A.MaxSize) A.array=(T*)realloc(A.array,(A.length+MAX)*sizeof(T)); A.array[++A.length]=key; }} {}};classNoMem{public: NoMem() {} virtual~NoMem() {}};//異常拋出，太麻煩不寫(xiě)intmain(){ MaxHeap<T>H(MAX); cout<<"1.初始化輸入數(shù)據(jù)"<<endl; cout<<"2.插入數(shù)據(jù)"<<endl; cout<<"3.查找數(shù)據(jù)"<<endl; cout<<"4.刪除數(shù)據(jù)"<<endl; cout<<"5.遍歷數(shù)據(jù)"<<endl; cout<<"0.退出"<<endl; cin>>choose; switch(choose) { case1: GetArrayKey(A);//初始化數(shù)據(jù) H.Initialize(A.array,A.length); H.heapAdjust(); break; case2: //插入元素 cout<<"請(qǐng)輸入您想要插入的元素的值"<<endl; cin>>x; H.Insert(x); cout<<"插入成功"<<endl;break; case3:x=H.Max();//求最大元素 cout<<"當(dāng)前查找最大的元素為："<<x<<endl; break; }} return0;}數(shù)據(jù)結(jié)構(gòu)選擇：定義T為INT類型，權(quán)值為INT類型，定義一個(gè)class，里面一個(gè)privateT*heap，采用大頂堆的方法實(shí)現(xiàn)函數(shù)功能，函數(shù)實(shí)現(xiàn)都是在class里面的public函數(shù);算法實(shí)現(xiàn):在class里面實(shí)現(xiàn)全部函數(shù)，函數(shù)定義為public一個(gè)初始化initialize(Ta[],intsize),把一個(gè)數(shù)組直接覆蓋掉原來(lái)的T*heap，并執(zhí)行相應(yīng)的長(zhǎng)度變化操作.一個(gè)查找最大元素TMax()：返回第一個(gè)數(shù)組元素一個(gè)遍歷voidLoadHeap()：采用從頭到尾遍歷整個(gè)數(shù)組元素一個(gè)求元素?cái)?shù)組的長(zhǎng)度intSize()：返回當(dāng)前長(zhǎng)度總結(jié)：由于編寫(xiě)優(yōu)