本篇文章的主要内容是用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); 

Tags: PHP堆排序原理

分享到：