欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

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