蜘蛛  安装  锁定  WP  时间  组件  跳转  dl

您所在的位置:小祥子 » 编程 » PHP » 正文

php实现堆排序算法

时间:2015-03-29 编辑:佚名 来源:互联网

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆,是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值,即A[PARENT[i]] >= A[i]。在数组的非降序排序中,需要使用的就是大根堆,因为根据大根堆的要求可知,最大的值一定在堆顶。

abstract class Heap {
    protected $elements = array();
    protected $n = 0;
   
    public abstract function insert($element);

    public function isEmpty() {
        return $this->n==0;
    }
   
    public function all(){
        return $this->elements;
    }

    /**
     * Extract the top value of the heap
     *
    */
    public function extract() {
        $element = $this->elements[1];
        $this->elements[1] = array_pop($this->elements);
        $this->n--;
        $this->siftDown();
        return $element;
    }
   
    /**
     * Rearranges the heap after an extraction to keep the heap property
     */
    protected abstract function siftDown();

    /**
     * Swap two elements on the elements array
     *
     */
    protected function swap($x,$y) {
        $tmp = $this->elements[$x];
        $this->elements[$x] = $this->elements[$y];
        $this->elements[$y] = $tmp;
    }
}
class MinHeap extends Heap {
   
    public function insert($element) {
        $this->elements[++$this->n] = $element;
        for ($i = $this->n; $i > 1 && $this->elements[$i >> 1] > $this->elements[$i]; $i = $i >> 1)
            $this->swap($i >> 1,$i);
    }
    protected function siftDown() {
        for ($i = 1; ($c = $i * 2) <= $this->n; $i = $c) {
            //Checks which of the smaller child to compare with the parent
            if ($c+1 <= $this->n && $this->elements[$c+1] < $this->elements[$c])
                $c++;
            if ($this->elements[$i] < $this->elements[$c])
                break;
            $this->swap($c, $i);
        }
    }

}

function heapSort($array){
    $heap=new MinHeap();
    foreach($array as $val){
        $heap->insert($val);
       
    }   
    $arr=array();
    while(!$heap->isEmpty()){
        $arr[]=$heap->extract();
    }   
    return $arr;
}
$array=array(1,13,8,4,5);
$arr=heapSort($array);
print_r($arr);

关键词:排序 算法 堆排序