文档章节

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

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

参考自: 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
博文 139
码字总数 35074
作品 1
浦东
程序员
PHP视频教程搜集整理分享【www.eaglephp.com】

1、PHP视频教程 (第一讲) PHP环境搭配和代码调试 2、PHP视频教程 (第二讲) PHP的数据类型 源码调试 3、PHP视频教程 (第三讲) 常用PHP运算类型介绍与应用 4、PHP视频教程 (第四讲) PHP条件语句...

maoxiaojian
2013/02/28
447
5
现货!《PHP7实践指南:o2o网站与App后台开发》京东天猫有售

终于发售了,啥也不想说了,喜欢的或需要的就点击 链接 进去购买吧。 另外此书将作为 2017 PHP全球开发者大会 现场活动用书 天猫购书 包邮 PHP7实践指南:O2O网站与App后台开发 数据库设计 PH...

szxy1234
2017/11/02
0
0
Perfmon.exe辅助检查.NET程序内存泄漏

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

北风其凉
2014/07/30
0
0
MoreWindows博客目录(微软最有价值专家,原创技术文章152篇)

为了方便大家查找和学习,现将本人博客中所有博客文章列出目录。 一. 白话经典算法 目前有17篇,分为七大排序和经典面试题讲解两大类 1. 《白话经典算法系列之一 冒泡排序的三种实现》 2. 《...

morewindows
2013/12/24
0
0
JSON进阶第二篇 AJAX方式传递JSON数据

上一篇《JSON进阶第一篇 在PHP与javascript 中使用JSON》示范了在PHP和javascript中如何使用JSON类型的数据,本篇将介绍用AJAX方式得到JSON数据从而动态生成标题和提示语句。这种技术在静态页...

晨曦之光
2012/05/21
75
0
JSON进阶第二篇 AJAX方式传递JSON数据

上一篇《JSON进阶第一篇 在PHP与javascript 中使用JSON》示范了在PHP和javascript中如何使用JSON类型的数据,本篇将介绍用AJAX方式得到JSON数据从而动态生成标题和提示语句。这种技术在静态页...

长平狐
2012/12/10
35
0
JSON进阶第二篇 AJAX方式传递JSON数据

上一篇《JSON进阶第一篇 在PHP与javascript 中使用JSON》示范了在PHP和javascript中如何使用JSON类型的数据,本篇将介绍用AJAX方式得到JSON数据从而动态生成标题和提示语句。这种技术在静态页...

彭博
2012/04/12
383
0
PHP三小时入门笔记(2014-9-3)

PHP三小时入门笔记(2014-9-3) 1、PHP是什么:编程语言 2、PHP 代码是运行在服务端的 3、行该脚本后,客户端就能接收到其结果,但他们无法得知其背后的代码是如何运作的 4、甚至可以将 web ...

GZhiDao
2015/11/26
42
0
ThinkPHP5开发的正确姿势——PHP最佳实践的参考规范

安装篇 使用composer,既然是趋势就早日拥抱,能写PHP的这点工具用不来说不过去(另外官方的所有扩展都会以composer方式提供); 如果只需要核心单独安装核心框架就行了,应用仓库并非必须;...

小和
2016/11/13
381
0
swoole项目思维转换 -- 前篇

PHP是最好的语言,Swoole重新定义了最好的语言,这当然是个梗了,不过php做为一个入门低、开发快、执行效率高的一门语言,而在以快速著称的pc互联网时代,无可争议的成为首选,这是php的优势...

杨太化
2015/10/15
626
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

聊聊spring cloud的AsyncLoadBalancerAutoConfiguration

序 本文主要研究一下AsyncLoadBalancerAutoConfiguration AsyncLoadBalancerAutoConfiguration spring-cloud-commons-2.0.0.RELEASE-sources.jar!/org/springframework/cloud/client/loadba......

go4it
14分钟前
0
0
10.19 iptables规则备份和恢复 ,firewalld的9个zone,service的操作

保存和备份iptables规则 内容: 保存iptables规则 service iptables save 把iptables规则备份到my.ipt文件中: iptables-save > my.ipt 恢复刚才备份的规则: iptables-restore < my.ipt 1.......

Linux_老吴
17分钟前
0
0
Vue 自动化表单相关资料

1.使用vue自动化表单 2.Vue可视化,Vue代码生成,Vue动态表单 3.前端表单进阶之路:通过 Vue.js 实现表单可配置化 4.使用Vue动态生成form表单 5.autoform-devtool...

IT追寻者
18分钟前
0
0
动态SQL

一、动态SQL 1、if <select id="findActiveBlogWithTitleLike" resultType="Blog"> SELECT * FROM BLOG WHERE state = ‘ACTIVE’ <if test="title != null"> AND title l......

一个yuanbeth
20分钟前
0
0
使用ExternalDNS自动化DNS配置

Kubernetes社区的生态繁荣和该领域技术的快速茁壮发展,已经是众所周知。Kubernetes领域有太多强大的、创新的技术产品,而最近引起我注意的项目是ExternalDNS。这是在近期的POC期间客户主动咨...

RancherLabs
25分钟前
0
0
多线程-Lock

今天写了一段测试Lock的代码,如下: namespace TLock{ class Program { static void Main(string[] args) { TMyThread myThread = new TMyThre......

kaixinguo314
35分钟前
0
0
如何清洁你脏兮兮的笔记本电脑?

简评:我还以为清理笔记本就是吹灰。 本文转自纽约时报(中文版),原文见文末。 你知道你的笔记本电脑很脏。你可以看到键盘上的灰尘和污垢,以及触控板中间的皮肤油印。那你上次清洁它是什么...

极光推送
40分钟前
0
0
中国经济模式转型的挑战

  中国经济模式转型的挑战   陈志武(耶鲁大学金融经济学教授)   今天我讲的题目是当前大家关心的,特别是这次金融危机之后,中国学界、决策层还有民间,都很关注中国以后的走向,社会...

吕伯文
45分钟前
2
0
win10玩docker无法Share Drivers的坑

Win10下使用Docker的开启Shared Drivers的时候,一直卡在:Sharing Drivers。 原因如下: 1.检查操作性系统的net share功能开启了没有 cmd-->services.msc 查看Server和Workstation两个S...

傲娇字符
46分钟前
0
0
Intellij Idea快捷键的使用

Ctrl +H 全文搜索 快捷键模式Eclipse Alt +左箭头 上一个方法 Alt + 右箭头 下一个方法 Ctrl + 左键点击文件title 提示文件路径 参考资料 http://wiki.jikexueyuan.com/project/intellij-ide...

轩辕剑
51分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部