針對堆排序的概念自己百度去，今天沒事了用php實現堆排序的算法
1 abstract class Heap {
2 protected $elements = array();
3 protected $n = 0;
4
5 public abstract function insert($element);
6
7 public function isEmpty() {
8 return $this->n==0;
9 }
10
11 public function all(){
12 return $this->elements;
13 }
14
15 /**
16 * Extract the top value of the heap
17 *
18 */
19 public function extract() {
20 $element = $this->elements[1];
21 $this->elements[1] = array_pop($this->elements);
22 $this->n--;
23 $this->siftDown();
24 return $element;
25 }
26
27 /**
28 * Rearranges the heap after an extraction to keep the heap property
29 */
30 protected abstract function siftDown();
31
32 /**
33 * Swap two elements on the elements array
34 *
35 */
36 protected function swap($x,$y) {
37 $tmp = $this->elements[$x];
38 $this->elements[$x] = $this->elements[$y];
39 $this->elements[$y] = $tmp;
40 }
41 }
42 class MinHeap extends Heap {
43
44 public function insert($element) {
45 $this->elements[++$this->n] = $element;
46 for ($i = $this->n; $i > 1 && $this->elements[$i >> 1] > $this->elements[$i]; $i = $i >> 1)
47 $this->swap($i >> 1,$i);
48 }
49 protected function siftDown() {
50 for ($i = 1; ($c = $i * 2) <= $this->n; $i = $c) {
51 //Checks which of the smaller child to compare with the parent
52 if ($c+1 <= $this->n && $this->elements[$c+1] < $this->elements[$c])
53 $c++;
54 if ($this->elements[$i] < $this->elements[$c])
55 break;
56 $this->swap($c, $i);
57 }
58 }
59
60 }
61
62 function heapSort($array){
63 $heap=new MinHeap();
64 foreach($array as $val){
65 $heap->insert($val);
66
67 }
68 $arr=array();
69 while(!$heap->isEmpty()){
70 $arr[]=$heap->extract();
71 }
72 return $arr;
73 }
74 $array=array(1,13,8,4,5);
75 $arr=heapSort($array);
76 print_r($arr);
