PHP 堆与堆排序的详解

堆排序：堆排序是利用堆的性质进行的一种选择排序。下面先讨论一下堆。

1.堆

堆实际上是一棵完全二叉树，其任何一非叶节点满足性质：

Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2]

即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。

堆分为大顶堆和小顶堆，满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆，满足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。

2.堆排序的思想

利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。

其基本思想为(大顶堆)：

1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无须区；

2)将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];

3)由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

操作过程如下：

1)初始化堆：将R[1..n]构造为堆；

2)将当前无序区的堆顶元素R[1]同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。

因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。

堆排序与快速排序，归并排序一样都是时间复杂度为O(N*logN)的几种常见排序方法。学习堆排序前，先讲解下什么是数据结构中的二叉堆。

PHP 堆管理代码如下：

1. class heep{ 
2.  static function add(&$arr,$one){ 
3.   $arr[] = $one; 
4.   self::up($arr,count($arr) -1); 
5.  } 
6.  // 下沉 
7.  static function del(&$arr){ 
8.   $arr[0] = array_pop($arr); 
9.   self::down($arr,0,count($arr)-1); 
10.  } 
11.  static function swap(&$arr,$i,$p){ 
12.   $tmp = $arr[$i]; 
13.   $arr[$i] = $arr[$p]; 
14.   $arr[$p] = $tmp; 
15.  } 
16.  // 增加元素 上浮 
17.  static function up(&$arr,$i){ 
18.   $p = floor(($i-1)/2); 
19.   while( $p >= 0 && $i > 0 && $arr[$p] > $arr[$i] ){ 
20.    self::swap($arr,$i,$p); 
21.    $i = $p; 
22.    $p = floor(($i-1)/2); 
23.   } 
24.  } 
25.  // 下沉 $i开始 $n结束 
26.  static function down(&$arr,$i,$n){ 
27.   $l = 2*$i + 1; 
28.   while( $l <= $n ){ 
29.    if( $l+1 <= $n && $arr[$l+1]<$arr[$l]) $l ++; 
30.    if( $arr[$l] > $arr[$i] ) break; 
31.    self::swap($arr,$i,$l); 
32.    $i = $l; 
33.    $l = 2*$i + 1; 
34.   } 
35.  } 
36.  // 将数组变成堆 
37.  static function make(&$arr){  
38.   $n = count( $arr )-1; 
39.      for ($i = $n / 2 - 1; $i >= 0; $i--)  
40.          self::down($arr,$i,$n); 
41.  } 
42.  // 将堆进行排序 
43.  static function sort(&$arr){  
44.   $n = count( $arr )-1; 
45.      for ( $i=$n; $i >= 0; $i--){ 
46.       self::swap($arr,0,$i); 
47.          self::down($arr,0,$i-1); 
48.      } 
49.  } 
50. } 
51.  
52. $arr = [10,40,30]; 
53. $arr = array(); 
54.  
55. heep::add($arr,40); 
56. heep::add($arr,10); 
57. heep::add($arr,30); 
58. heep::add($arr,15); 
59. heep::add($arr,8); 
60. heep::add($arr,50); 
61. heep::add($arr,20); 
62. heep::add($arr,3); 
63.  
64. echo join(',',$arr),'<br>'; 
65.  
66. heep::del($arr); 
67. heep::del($arr); 
68. heep::del($arr); 
69. echo join(',',$arr),'<br>'; 
70. //Vevb.com 
71. heep::sort($arr); 
72. echo join(',',$arr),'<br>'; 
73.  
74. $arr = [40,10,30]; 
75. heep::make($arr); 
76. echo join(',',$arr),'<br>'; 

假设n为当前数组的key则,n的父节点为 n>>1 或者 n/2(整除);n的左子节点l= n<<1 或 l=n*2,n的右子节点r=(n<<1)+1 或 r=l+1,代码如下:

$arr=array(1,8,7,2,3,4,6,5,9);

数组$arr的原形态结构如下:

1. 1 
2. / 
3. 8 7 
4. / / 
5. 2 3 4 6 
6. / 
7. 5 9 

heapsort($arr);print_r($arr);

排序后生成标准的小顶堆结构如下:

1. 1 
2. / 
3. 2 3 
4. / / 
5. 4 5 6 7 
6. / 
7. 8 9 

既数组:array(1,2,3,4,5,6,7,8,9):代码如下:

1. function heapsort(&$arr) 
2. { 
3. //求最后一个元素位 
4. $last=count($arr); 
5. //堆排序中通常忽略$arr[0] 
6. array_unshift($arr,0); 
7. //最后一个非叶子节点 
8. $i=$last>>1; 
9.  
10. //整理成大顶堆,最大的数整到堆顶,并将最大数和堆尾交换,并在之后的计算中忽略数组后端的最大数(last),直到堆顶(last=堆顶) 
11. while(true) 
12. { 
13. adjustnode($i,$last,$arr); 
14. if($i>1) 
15. { 
16. //移动节点指针,遍历所有非叶子节点 
17. $i--; 
18. } 
19. else 
20. { 
21. //临界点last=1,既所有排序完成 
22. if($last==1)break; 
23. //当i为1时表示每一次的堆整理都将得到最大数(堆顶,$arr[1]),重复在根节点调整堆 
24. swap($arr[$last],$arr[1]); 
25. //在数组尾部按大小顺序保留最大数,定义临界点last,以免整理堆时重新打乱数组后面已排序好的元素 
26. $last--; 
27. } 
28. } 
29. //弹出第一个数组元素 
30. array_shift($arr); 
31. } 
32.  
33. //整理当前树节点($n),临界点$last之后为已排序好的元素 
34. function adjustnode($n,$last,&$arr) 
35. { 
36. $l=$n<<1; //$n的左孩子位 
37. if(!isset($arr[$l])||$l>$last) return ; 
38. $r=$l+1; //$n的右孩子位 
39.  
40. //如果右孩子比左孩子大,则让父节点的右孩子比 
41. if($r<=$last&&$arr[$r]>$arr[$l]) $l=$r; 
42. //如果其中子节点$l比父节点$n大,则与父节点$n交换 
43. if($arr[$l]>$arr[$n]) 
44. { 
45. //子节点($l)的值与父节点($n)的值交换 
46. swap($arr[$l],$arr[$n]); 
47. //交换后父节点($n)的值($arr[$n])可能还小于原子节点($l)的子节点的值,所以还需对原子节点($l)的子节点进行调整,用递归实现 
48. adjustnode($l,$last,$arr); 
49. } 
50. } 
51.  
52. //交换两个值 
53. function swap(&$a,&$b) 
54. { 
55. $a=$a ^ $b; 
56. $b=$a ^ $b; 
57. $a=$a ^ $b; 
58. }