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);
转载于:https://www.cnblogs.com/CHEUNGKAMING/p/4377449.html
相关资源：PHP实现的堆排序算法详解
