本篇文章的主要內容是用PHP實現堆排序，具有一定的參考價值，感興趣的朋友可以了解一下。

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

2.給出某個結點的下標,可以計算出父結點的和孩子結點的下標; parent(i)=floor(i/2) left(i)=2i right=2i+1

3.最大堆和最小堆,最大堆:根結點是最大值,最小堆:根結點是最小值

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

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

1. maxHeapify (array,index,heapSize) //最大堆調整 
2.  
3.     iMax,iLeft,iRight 
4.  
5.     while true 
6.  
7.         iMax=index;iLeft=2*index+1;iRight=2*index+2 
8.  
9.         如果根結點小于左右子樹里結點值,就交換一下這兩個值 
10.  
11.         利用第三方變量,交換下兩個值 
12.  
13. buildMaxHeap(array) //創建最大堆,把一個數組調整成最大堆的數組 
14.  
15.     iParent=floor((size-1)/2) 
16.  
17.     for i=iParent;i>=0;i-- 
18.  
19.         maxHeapify (array,i,size) 
20.  
21. sort(arr) 
22.  
23.     buildMaxHeap(array, heapSize);//創建最大堆 
24.  
25.     for (int i = heapSize - 1; i > 0; i--) { 
26.  
27.         swap(array, 0, i); //交換第一個和最后一個 
28.  
29.          maxHeapify(array, 0, i);//維護最大堆,size小了一個  
30.  
31. //交換元素 
32.  
33. function swap(&$arr,$a,$b){ 
34.  
35.         $temp=$arr[$a]; 
36.  
37.         $arr[$a]=$arr[$b]; 
38.  
39.         $arr[$b]=$temp; 
40.  
41. } 
42.  
43. //排序的入口函數 
44.  
45. function heapSort(&$arr){ 
46.  
47.         $heapSize=count($arr); 
48.  
49.         buildMaxHeap($arr, $heapSize);//創建最大堆 
50.  
51.         for ($i = $heapSize - 1; $i > 0; $i--) { 
52.  
53.                 swap($arr,0,$i); //交換第一個和最后一個 
54.  
55.                 maxHeapify($arr, 0, $i);//維護最大堆,size小了一個 
56.  
57.         }    
58.  
59. } 
60.  
61. //創建最大堆的函數 
62.  
63. function buildMaxHeap(&$arr, $heapSize){ 
64.  
65.         $iParent=floor(($heapSize-1)/2);//根據最后一個元素的索引值計算該結點根結點的索引是哪個 
66.  
67.         for($i=$iParent;$i>=0;$i--){//這個循環是循環的所有根結點 
68.  
69.                 maxHeapify($arr,$i,$heapSize);//維護最大堆 
70.  
71.         }    
72.  
73. } 
74.  
75. //維護最大堆 
76.  
77. function maxHeapify(&$arr,$index,$heapSize){ 
78.  
79.         $iMax=0;$iLeft=0;$iRight=0; 
80.  
81.         while(true){ 
82.  
83.                 $iMax=$index; 
84.  
85.                 $iLeft=2*$iMax+1; 
86.  
87.                 $iRight=2*$iMax+2; 
88.  
89.                 if($iLeft<$heapSize && $arr[$iLeft]>$arr[$iMax]){ 
90.  
91.                         $iMax=$iLeft; 
92.  
93.                 }    
94.  
95.                 if($iRight<$heapSize && $arr[$iRight]>$arr[$iMax]){ 
96.  
97.                         $iMax=$iRight; 
98.  
99.                 }    
100.  
101.                 if($iMax!=$index){ 
102.  
103.                         swap($arr,$index,$iMax); 
104.  
105.                         $index=$iMax; 
106.  
107.                 }else{ 
108.  
109.                         break; 
110.  
111.                 }    
112.  
113.         }    
114.  
115. } 
116.  
117. $arr=array(2,1,3,5,9,6); 
118.  
119. heapSort($arr); 
120.  
121. var_dump($arr);