時(shí)間復(fù)雜度為O(nlogn)，思路就是從最后一個(gè)非葉結(jié)點(diǎn)開(kāi)始，依次往回遍歷每個(gè)結(jié)點(diǎn)，將以該結(jié)點(diǎn)為根的子樹(shù)建立成大根堆，直到遍歷到整棵完全二叉樹(shù)的根結(jié)點(diǎn)時(shí)為止，此時(shí)整棵樹(shù)為大根堆。

以當(dāng)前結(jié)點(diǎn)為根的子樹(shù)建立大根堆：

//向下調(diào)整,將該結(jié)點(diǎn)的子樹(shù)變成大根堆 void AdjustDown(int A[],int k,int len){ //k為根結(jié)點(diǎn)編號(hào)，len為數(shù)組長(zhǎng)度 int i,j;A[0]=A[k];for(j=2*k;j<=len;j*=2){if(j<len&&A[j]<A[j+1]) //右孩子較大j++;if(A[0]<A[j]){A[k]=A[j];k=j; }else break;}A[k]=A[0]; }

堆排序算法：

//堆排序算法 void HeapSort(int A[],int len){int i,temp;for(i=len/2;i>=1;i--) //建立初始大根堆AdjustDown(A[],i,len); //從len/2到1，反復(fù)調(diào)整堆for(i=len;i>1;i--){temp=A[1];A[1]=A[i];A[i]=temp; //把最大的元素放到了最后面，最終排序結(jié)果為由小到大AdjustDown(A[],1,i-1); //把剩余i-1個(gè)元素整理成堆} }

這樣排序的結(jié)果為由小到大！?

如果插入元素的話，直接插入到最后的位置，然后將插入的元素向上調(diào)整，直到整棵樹(shù)再次變成大根堆時(shí)為止！

向上調(diào)整的代碼：

//插入元素到最后位置，需要向上調(diào)整建立大根堆 void AdjustUp(int A[],int len){A[0]=A[len];int i=len/2,j=len;while(i>0&&A[i]<A[0]){A[j]=A[i]; //雙親結(jié)點(diǎn)下調(diào)j=i;i/=2; //繼續(xù)向上比較 }A[j]=A[0]; }

?

總結(jié)

以上是生活随笔為你收集整理的堆排序分析（大根堆为例，由小到大排序）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。