php实现堆排序
程序员文章站
2024-01-23 19:08:52
...
针对堆排序的概念自己百度去,今天没事了用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
上一篇: 金山毒霸怎么设置禁止访问指定网站?