php实现堆排序，php堆排序_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);