文档章节

PHP开发中的数据类型 ( 第3篇 ) :Heaps

帖子列表
 帖子列表
发布于 2014/06/18 17:01
字数 795
阅读 45
收藏 3

参考自: http://www.sitepoint.com/data-structures-3/ (Published July 22, 2013)

heaps 大概翻译成垛比较好吧,意思是许多、一堆(但不是stack的堆),heaps有几种类型,这里介绍一种叫做 binary maxheap : (binary:因为只有且必须有两个子节点、maxheap:因为任何父节点都比子节点的值大)。所以我的理解是它很像Tree,但是相比Tree而言,还有既定的顺序等。

Heaps也是table的一种形式,所以也有以下几种基本操作:

- 新建,即新建一个heap

- isEmpty,即检查是否heap为空
- insert,即向heap添加一个项目
- extract,即从heap中移除最顶端的那个项目

下面的代码实现了一个heap:

class BinaryHeap
{
    protected $heap;
 
    public function __construct() {
        $this->heap  = array();
    }
 
    public function isEmpty() {
        return empty($this->heap);
    }
 
    public function count() {
        // returns the heapsize
        return count($this->heap) - 1;
    }
 
    public function extract() {
        if ($this->isEmpty()) {
            throw new RunTimeException('Heap is empty');
        }
 
        // extract the root item
        $root = array_shift($this->heap);
 
        if (!$this->isEmpty()) {
            // move last item into the root so the heap is
            // no longer disjointed
            $last = array_pop($this->heap);
            array_unshift($this->heap, $last);
 
            // transform semiheap to heap
            $this->adjust(0);
        }
 
        return $root;
    }
 
    public function compare($item1, $item2) {
        if ($item1 === $item2) {
            return 0;
        }
        // reverse the comparison to change to a MinHeap!
        return ($item1 > $item2 ? 1 : -1);
    }
 
    protected function isLeaf($node) {
        // there will always be 2n + 1 nodes in the
        // sub-heap
        return ((2 * $node) + 1) > $this->count();
    }
 
    protected function adjust($root) {
        // we've gone as far as we can down the tree if
        // root is a leaf
        if (!$this->isLeaf($root)) {
            $left  = (2 * $root) + 1; // left child
            $right = (2 * $root) + 2; // right child
 
            // if root is less than either of its children
            $h = $this->heap;
            if (
              (isset($h[$left]) &&
                $this->compare($h[$root], $h[$left]) < 0)
              || (isset($h[$right]) &&
                $this->compare($h[$root], $h[$right]) < 0)
            ) {
                // find the larger child
                if (isset($h[$left]) && isset($h[$right])) {
                  $j = ($this->compare($h[$left], $h[$right]) >= 0)
                      ? $left : $right;
                }
                else if (isset($h[$left])) {
                  $j = $left; // left child only
                }
                else {
                  $j = $right; // right child only
                }
 
                // swap places with root
                list($this->heap[$root], $this->heap[$j]) =
                  array($this->heap[$j], $this->heap[$root]);
 
                // recursively adjust semiheap rooted at new
                // node j
                $this->adjust($j);
            }
        }
    }

    public function insert($item) {
        // insert new items at the bottom of the heap
        $this->heap[] = $item;
     
        // trickle up to the correct location
        $place = $this->count();
        $parent = floor($place / 2);
        // while not at root and greater than parent
        while (
          $place > 0 && $this->compare(
            $this->heap[$place], $this->heap[$parent]) >= 0
        ) {
            // swap places
            list($this->heap[$place], $this->heap[$parent]) =
                array($this->heap[$parent], $this->heap[$place]);
            $place = $parent;
            $parent = floor($place / 2);
        }
    }    
}

向结构中插入一些数据:

$heap = new BinaryHeap();
$heap->insert(19);
$heap->insert(36);
$heap->insert(54);
$heap->insert(100);
$heap->insert(17);
$heap->insert(3);
$heap->insert(25);
$heap->insert(1);
$heap->insert(67);
$heap->insert(2);
$heap->insert(7);

把heap打印出来的结果是下面这样的,完全没有任何规律:

Array
(
    [0] => 100
    [1] => 67
    [2] => 54
    [3] => 36
    [4] => 19
    [5] => 7
    [6] => 25
    [7] => 1
    [8] => 17
    [9] => 2
    [10] => 3
)

但是如果把项目extract操作一下,就按照顺序排列了:

while (!$heap->isEmpty()) {
    echo $heap->extract() . "n";
} 

100
67
54
36
25
19
17
7
3
2
1

PHP内置的heap: SplMaxHeap and SplMinHeap

class MyHeap extends SplMaxHeap
{
    public function compare($item1, $item2) {
        return (int) $item1 - $item2;
    }
}

PHP内置的heap: SplPriorityQueue

class PriQueue extends SplPriorityQueue
{
    public function compare($p1, $p2) {
        if ($p1 === $p2) return 0;
        // in ascending order of priority, a lower value
        // means higher priority
        return ($p1 < $p2) ? 1 : -1;
   }
}
$pq = new PriQueue();
$pq->insert('A', 4);
$pq->insert('B', 3);
$pq->insert('C', 5);
$pq->insert('D', 8);
$pq->insert('E', 2);
$pq->insert('F', 7);
$pq->insert('G', 1);
$pq->insert('H', 6);
$pq->insert('I', 0);
  
while ($pq->valid()) {
    print_r($pq->current());
    echo "n";
    $pq->next();
}

结果:

I
G
E
B
A
C
H
F
D
// extract just the priority
$pq->setExtractFlags(SplPriorityQueue::EXTR_PRIORITY);
 
// extract both data and priority (returns an associative
// array for each element)
$pq->setExtractFlags(SplPriorityQueue::EXTR_BOTH);

EOF

© 著作权归作者所有

共有 人打赏支持
帖子列表

帖子列表

粉丝 114
博文 140
码字总数 35207
作品 1
浦东
程序员
买《Python从小白到大牛》专题视频课程,送配套纸质图书

经过一年多时间的呕心沥血,Python立体化图书——《Python从小白到大牛》即将与大家见面了。所谓立体化图书包括:电子图书、视频、课件和服务等内容。 《Python从小白到大牛》纸质图书将于9...

tony关东升
07/23
0
0
Perfmon.exe辅助检查.NET程序内存泄漏

因为工作用C#写的程序老是内存泄漏,在网上找了找资料后,发现了Windows自带的性能监视器Perfmon.exe可以辅助查看.NET程序的运行状况。今天研究了一番,下面的内容就是一些我认为比较重要需要...

北风其凉
2014/07/30
0
0
PHP最佳实践之过滤、验证、转义和密码

过滤、验证和转义 1).不要相信任何来自不受自己直接控制的数据源中的数据。包括但不限于: $_GET $_POST $_REQUEST $_COOKIE $argv php://stdin php://input filegetcontents() 远程数据库 ...

肖潇_
2017/07/12
0
0
使用Entity Framework和WCF Ria Services开发SilverLight之2:POCO

在上一篇中《使用Entity Framework和WCF Ria Services开发SilverLight之1:简单模型》我们提出这类简单模型的几个问题: 1:实体模型被紧耦合在EDM中,同时它不能项目(模块)使用。随着每一...

luminji
2011/06/13
0
0
史上最简单的 MySQL 教程

温馨提示:本系列博文已经同步到 GitHub,如有需要的话,欢迎大家到「mysql-tutorial」进行和操作! 1 前言   数据库(Database)是按照数据结构来组织、存储和管理数据的仓库,它产生于距...

qq_35246620
2017/04/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Access denied for user 'root'@'localhost' 解决流程

ERROR 1698 (28000): Access denied for user 'root'@'localhost' 解决流程 基于debian 9 maridb 10 因为安装 时不知道 密码,所以在管理中下使用 mysqladmin -u root -p password ex(ex为密......

dragon_tech
39分钟前
0
0
nginx 负载均衡

一.配置方式 1.轮询(默认) 优点:实现简单; 缺点:不考虑每台服务器处理能力 2.权重 weight默认是1。如果有多个配置权重的节点,比较相对值。 15:10,只代表访问8080端口的概率是访问908...

imbiao
今天
3
0
jQuery学习笔记180923

jQuery 操作 CSS jQuery 拥有若干进行 CSS 操作的方法。我们将学习下面这些: addClass() - 向被选元素添加一个或多个类 removeClass() - 从被选元素删除一个或多个类 toggleClass() - 对被选...

颖伙虫
今天
2
0
[python] colorama 模块 - 改变控制台输出文本的颜色

除了使用 PyQt 这样的图形化开发框架外,基本上 python 程序都是跑在控制台中的。很多时候,单纯使用黑白的文字不能很好地突出我们要显示的信息。有时候我们需要将错误的提示使用红色标注,而...

cometeme
今天
3
0
Makefile 学习 2 - 基于若干 Blog 的汇总

基于若干 Blog 汇总的 makefile 教程 陈皓 https://blog.csdn.net/haoel/article/details/2886 Makefile 进阶 1. Makefile 中的内容 显式规则。显式规则说明了,如何生成一个或多的的目标文件...

公孙衍
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部