1.堆(二叉堆):可以視為一棵完全的二叉樹,除了最底層之外,每一層都是滿的,這使得堆可以利用數組來表示,每一個結點對應數組中的一個元素

2.給出某個結點的下標,可以計算出父結點的和孩子結點的下標; parent(i)=floor(i/2) left(i)=2i right=2i+1
3.最大堆和最小堆,最大堆:根結點是最大值,最小堆:根結點是最小值

4.堆排序就是把最大堆堆頂的最大數取出,剩余的堆繼續調整為最大堆,再次將堆頂的最大數取出,直到剩余數只有一個結束

5.最大堆調整(維護最大堆,子節點永遠小于父結點) ;創建最大堆(把一個數組調整成最大堆的數組);堆排序(創建最大堆,交換,維護最大堆)

maxHeapify (array,index,heapSize) //最大堆調整 iMax,iLeft,iRight while true iMax=index;iLeft=2*index+1;iRight=2*index+2 如果根結點小于左右子樹里結點值,就交換一下這兩個值 利用第三方變量,交換下兩個值buildMaxHeap(array) //創建最大堆,把一個數組調整成最大堆的數組 iParent=floor((size-1)/2) for i=iParent;i i-- maxHeapify (array,i,size)sort(arr) buildMaxHeap(array, heapSize);//創建最大堆 for (int i = heapSize - 1; i i--) { swap(array, 0, i); //交換第一個和最后一個 maxHeapify(array, 0, i);//維護最大堆,size小了一個

//交換元素function swap( $arr,$a,$b){ $temp=$arr[$a]; $arr[$a]=$arr[$b]; $arr[$b]=$temp;//排序的入口函數function heapSort( $arr){ $heapSize=count($arr); buildMaxHeap($arr, $heapSize);//創建最大堆 for ($i = $heapSize - 1; $i $i--) { swap($arr,0,$i); //交換第一個和最后一個 maxHeapify($arr, 0, $i);//維護最大堆,size小了一個//創建最大堆的函數function buildMaxHeap( $arr, $heapSize){ $iParent=floor(($heapSize-1)/2);//根據最后一個元素的索引值計算該結點根結點的索引是哪個 for($i=$iParent;$i $i--){//這個循環是循環的所有根結點 maxHeapify($arr,$i,$heapSize);//維護最大堆//維護最大堆function maxHeapify( $arr,$index,$heapSize){ $iMax=0;$iLeft=0;$iRight=0; while(true){ $iMax=$index; $iLeft=2*$iMax+1; $iRight=2*$iMax+2; if($iLeft $heapSize $arr[$iLeft] $arr[$iMax]){ $iMax=$iLeft; if($iRight $heapSize $arr[$iRight] $arr[$iMax]){ $iMax=$iRight; if($iMax!=$index){ swap($arr,$index,$iMax); $index=$iMax; }else{ break;$arr=array(2,1,3,5,9,6);heapSort($arr);var_dump($arr);

相關教程：PHP視頻教程

以上就是【PHP】堆排序的原理以及實現代碼的詳細內容，PHP教程

鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯系我們修改或刪除，多謝。