php实现一个简单的堆

栏目: PHP · 发布时间: 7年前

内容简介:php实现一个简单的堆

主要介绍优先队列,通过优先队列引出堆, 然后写了一个类(php代码)实现了大根堆

原文请访问我的博客番茄技术小栈

优先队列

定义

优先队列是计算机科学中的一类抽象数据类型。优先队列中的每个元素都有各自的优先级,优先级最高的元素最先得到服务;优先级相同的元素按照其在优先队列中的顺序得到服务。优先队列往往用堆来实现。

特点

  • 普通队列:先进先出,后进后出
  • 优先队列:出队顺序和入队顺序无关,和优先级相关

现实用途

  • 动态任务处理中心(操作系统)

为什么使用优先队列

问题

  • 在1000000个元素中选出前100名
  • 在N个元素中选出前M个元素

解决方法

  • 排序,时间复杂度O(NlogN)
  • 使用优先队列:时间复杂度(NlogM)

优先队列的实现对比

php实现一个简单的堆

定义

堆的实现通过构造二叉堆(binary heap),实为二叉树的一种;由于其应用的普遍性,当不加限定时,均指该数据结构的这种实现。这种数据结构具有以下性质。

  • 任意节点小于(或大于)它的所有后裔,最小元(或最大元)在堆的根上(堆序性)。
  • 堆总是一棵完全树。即除了最底层,其他层的节点都被元素填满,且最底层尽可能地从左到右填入。
  • 将根节点最大的堆叫做最大堆或大根堆,根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
php实现一个简单的堆

用数组存储二叉堆

php实现一个简单的堆

代码实现

<?php
require('../Library/SortTestHelper.php');
/**
 * 最大堆
 */
class MaxHeap{


	private $data;
	private $count;

	public function __construct(){
		$this->data = array();
		$this->count = 0;
	}


	// public function __construct($arr){
	// }

	public function insert($item){

		//从1开始
        $this->data[$this->count + 1] = $item;
        $this->_shiftUp($this->count+1);
        $this->count++;
    }

    public function  extractMax(){
        $ret = $this->data[1];
        swap( $this->data, 1 , $this->count);
        $this->count--;
        $this->_shiftDown(1);
        return $ret;
    }

    public function getMax(){
        return $this->data[1];
    }

    public function isEmpty(){
        return $this->count == 0;
    }

    public function getData(){
    	return $this->data;
    }

    /**
     * [_shiftUp 新加入到堆中的元素直接放在数组后面,再与父元素比较后交换位置,直到根节点]
     * @param  [type] $k [description]
     * @return [type]    [description]
     */
	private function _shiftUp($k){
		//如果叶子节点的值比父元素大交换位置,并更新k的值
        while( $k > 1 && $this->data[(int)($k/2)] < $this->data[$k] ){
            // swap( $this->data[(int)($k/2)], $this->data[$k] );
            swap( $this->data, (int)($k/2) , $k);
            $k = (int)($k/2);
        }
    }

    /**
     * [_shiftDown 元素出堆的时候,需要维护此时的堆依然是一个大根堆, 此时将数组元素的最后一个值与第一个值交换,后从上往下维护堆的性质]
     * @param  [type] $k [description]
     * @return [type]    [description]
     */
    private function _shiftDown($k){
    	//2k代表该节点的左子节点
        while( 2*$k <= $this->count ){
            $j = 2*$k;
            //判断右节点是否存在,并且右节点大于左节点
            if( $j+1 <= $this->count && $this->data[$j+1] > $this->data[$j] ) $j ++;
            if( $this->data[$k] >= $this->data[$j] ) break;
            // swap( $this->data[$k] , $this->data[$j] );
            swap( $this->data, $k , $j );
            $k = $j;
        }
    }
}

$head_obj = new MaxHeap();
$n = 10;
for ($i=0; $i < $n; $i++) {
	$head_obj -> insert(rand(0, 1000));
}

print_r($head_obj -> getData());

while (!$head_obj -> isEmpty()) {
	echo $head_obj -> extractMax()."\n";
}
?>

结果

生成的堆为:
Array
(
    [1] => 916
    [2] => 776
    [3] => 590
    [4] => 615
    [5] => 764
    [6] => 539
    [7] => 95
    [8] => 167
    [9] => 23
    [10] => 374
)
打印大根堆为:
916
776
764
615
590
539
374
167
95
23

以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

Operating System Algorithms

Operating System Algorithms

Nathan Adams、Elisha Chirchir / CreateSpace Independent Publishing Platform / 2017-4-21 / USD 39.15

Operating System Algorithms will walk you through in depth examples of algorithms that you would find in an operating system. Selected algorithms include process and disk scheduling.一起来看看 《Operating System Algorithms》 这本书的介绍吧!

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具