堆排序

堆排序概念

堆排序是利用堆这种数据结构而设计的一种排序算法。时间复杂度为O(nlogn)。

堆排序具有如下性质的完全二叉树:每个节点的值都大于或等于其左右孩子节点的值,称为最大堆;或每个节点都小于或者等于其左右孩子节点被称为最小堆。


对堆中的节点进行编号,将这种逻辑映射到数组中,如下:

堆排序的基本性质:
最大堆:左右子节点小于父节点
最小堆:左右子节点大于父节点

堆排序流程

1.构建最大堆
构建最大堆之前呈现效果如下

构建最大堆之后呈现效果如下:

保证了堆排序中的最大堆的性质。
2.堆排序算法实现
取出构建最大堆中的最大值,放在尾部
然后重新构建最大堆。

以此类推最终达到从小到大的排序效果,完成堆排序。

PHP实现堆排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
<?php
/**
*
*/
class HeapSort
{
public function __construct(&$arr) {
$arr_length = count($arr)-1;
$this->HeapMaxSort($arr,$arr_length);
}
private function HeapMaxSort(&$arr,$arr_length) {;
$this->BuildMaxHeap($arr,$arr_length);

for($i = $arr_length;$i >= 0; $i--) {
$this->swap($arr,$i,0);
$arr_length--;
$this->MaxHeapify($arr,0,$arr_length);
}
}
private function BuildMaxHeap(&$arr,$arr_length) {
$count = count($arr)-1;
for ($i = floor($count/2); $i >=0; $i--) {
$this->MaxHeapify($arr,$i,$arr_length);
}
}

public function MaxHeapify(&$arr,$i,$arr_length) {
$left = $this->left($i);
$right = $this->right($i);
if($left <= $arr_length && $arr[$left] >= $arr[$i]) {
$this->swap($arr,$i,$left);
$largest = $left;
} else {
$largest = $i;
}
if ($right <= $arr_length && $arr[$right] >= $arr[$largest]) {
$this->swap($arr,$largest,$right);
$largest = $right;
}
if ($largest != $i) {
$this->MaxHeapify($arr,$largest);
}

}
public function swap(&$arr,$exist,$largest) {
$temp = $arr[$exist];
$arr[$exist] = $arr[$largest];
$arr[$largest] = $temp;
}
private function left($i) {
return 2*$i+1;
}

private function right($i) {
return 2*$i+2;
}


}
$array = array(5,2,3,1,4,6);
$Heap_Model = new HeapSort($array);
var_dump($array);