The SplHeap class

(PHP 5 >= 5.3.0, PHP 7, PHP 8)

简介

The SplHeap class provides the main functionalities of a Heap.

类摘要

abstract class SplHeap implements Iterator, Countable {

/* 方法 */

protected compare(mixed $value1, mixed $value2): int

public count(): int

public current(): mixed

public extract(): mixed

public insert(mixed $value): bool

public isCorrupted(): bool

public isEmpty(): bool

public key(): int

public next(): void

public recoverFromCorruption(): bool

public rewind(): void

public top(): mixed

public valid(): bool

}

SplHeap::compare — Compare elements in order to place them correctly in the heap while sifting up
SplHeap::count — Counts the number of elements in the heap
SplHeap::current — Return current node pointed by the iterator
SplHeap::extract — Extracts a node from top of the heap and sift up
SplHeap::insert — Inserts an element in the heap by sifting it up
SplHeap::isCorrupted — Tells if the heap is in a corrupted state
SplHeap::isEmpty — Checks whether the heap is empty
SplHeap::key — Return current node index
SplHeap::next — Move to the next node
SplHeap::recoverFromCorruption — Recover from the corrupted state and allow further actions on the heap
SplHeap::rewind — Rewind iterator back to the start (no-op)
SplHeap::top — Peeks at the node from the top of the heap
SplHeap::valid — Check whether the heap contains more nodes

add a note

User Contributed Notes 3 notes

down

Michelangelo van Dam ¶

12 years ago


To have a good idea what you can do with SplHeap, I created a little example script that will show the rankings of Belgian soccer teams in the Jupiler League.

<?php
/**
 * A class that extends SplHeap for showing rankings in the Belgian
 * soccer tournament JupilerLeague
 */
class JupilerLeague extends SplHeap 
{
    /**
     * We modify the abstract method compare so we can sort our
     * rankings using the values of a given array
     */
    public function compare($array1, $array2)
    {
        $values1 = array_values($array1);
        $values2 = array_values($array2);
        if ($values1[0] === $values2[0]) return 0;
        return $values1[0] < $values2[0] ? -1 : 1;
    }
}

// Let's populate our heap here (data of 2009)
$heap = new JupilerLeague();
$heap->insert(array ('AA Gent' => 15));
$heap->insert(array ('Anderlecht' => 20));
$heap->insert(array ('Cercle Brugge' => 11));
$heap->insert(array ('Charleroi' => 12));
$heap->insert(array ('Club Brugge' => 21));
$heap->insert(array ('G. Beerschot' => 15));
$heap->insert(array ('Kortrijk' => 10));
$heap->insert(array ('KV Mechelen' => 18));
$heap->insert(array ('Lokeren' => 10));
$heap->insert(array ('Moeskroen' => 7));
$heap->insert(array ('Racing Genk' => 11));
$heap->insert(array ('Roeselare' => 6));
$heap->insert(array ('Standard' => 20));
$heap->insert(array ('STVV' => 17));
$heap->insert(array ('Westerlo' => 10));
$heap->insert(array ('Zulte Waregem' => 15));

// For displaying the ranking we move up to the first node
$heap->top();

// Then we iterate through each node for displaying the result
while ($heap->valid()) {
  list ($team, $score) = each ($heap->current());
  echo $team . ': ' . $score . PHP_EOL;
  $heap->next();
}
?>

This results in the following output:
Club Brugge: 21
Anderlecht: 20
Standard: 20
KV Mechelen: 18
STVV: 17
Zulte Waregem: 15
AA Gent: 15
G. Beerschot: 15
Charleroi: 12
Racing Genk: 11
Cercle Brugge: 11
Kortrijk: 10
Lokeren: 10
Westerlo: 10
Moeskroen: 7
Roeselare: 6

Hope this example paved the way for more complex implementations of SplHeap.

down

igorsantos07 at gmail dot com ¶

7 years ago


While Michelangelo Van Dam example (http://br2.php.net/manual/en/class.splheap.php#93930) is a great demonstration of what can be done with SplHeap, this implementation is exactly what SplPriorityQueue does - based on SplMaxHeap. If you're planning to copy that snippet, go no further! There's a SPL class that does exactly what you want :)

down

Anthony ¶

6 years ago


If you wish to build a true tree based heap, you can do so as follows (implemented with SplMinHeap, but could be SplMaxHeap if you wish for the opposite order of items):

The stucture that we're trying to represent:

         1
         |
+-----+--+--+-----+
|     |     |     |
2     3     4     5
|     |           |
+   +-+-+         +
|   |   |         |
7   6   8         9
                  |
                +-+-+
                |   |
               10   11

<?php
$h = new SplMinHeap();

// [parent, child]
$h->insert([9, 11]);
$h->insert([0, 1]);
$h->insert([1, 2]);
$h->insert([1, 3]);
$h->insert([1, 4]);
$h->insert([1, 5]);
$h->insert([3, 6]);
$h->insert([2, 7]);
$h->insert([3, 8]);
$h->insert([5, 9]);
$h->insert([9, 10]);

for ($h->top(); $h->valid(); $h->next()) {
    list($parentId, $myId) = $h->current();
    echo "$myId ($parentId)\n";
}
?>

As you iterate over the heap, the return data will be read as if you're reading a book; ie left to right, top to bottom. It will NOT follow the relationships.

So, the above code will output the following:

1 (0)
2 (1)
3 (1)
4 (1)
5 (1)
7 (2)
6 (3)
8 (3)
9 (5)
10 (9)
11 (9)

add a note

官方地址：https://www.php.net/manual/en/class.splheap.php

有任何技术问题请点击这里网站运营推广招聘

IT PHP 编程语言 Linux 开发编程科技 Elasticsearch HTML/CSS/XML 网络 JAVA NoSQL 数据库面试 C/C++ Golang Git 算法操作系统正则表达式 Redis 互联网 MySql JavaScript 运维软件国际架构设计 Mac OS TCP/IP Excel Vim Windows Socket Oracle VR MongoDB Python 运营 MemCache 商业硬件电子娱乐设计 nginx 摄影游戏 WordPress HTTP 团建数码电器

php7 安装fileinfo扩展 preg_split — 通过一个正则表达式分隔字符串 php位值,解决 PHP 中 usort 在值相同时改变原始位置的问题 [PHP] inet_pton/inet_ntop IP地址转换函数 array_multisort() 多字段排序 PHPMailer设置utf8 PHPMailer字符集CharSet ADORecordSet对象 PHP 8.1 [鸟哥]PHP_INT_MIN 和 -9223372036854775808 adodb手册 opcache预加载 Composer的Packagist资源 mysql面试题 php中几种注释规范 [原创]诡异的php-fpm超时问题 php扩展开发 laravel框架查看sql语句方式 PHP7 mcrypt替代方案 Packagist / Composer 中国全量镜像支持php7的性能采集扩展

略微加速

PHP官方手册 - 互联网笔记

The SplHeap class

简介

类摘要

目录

User Contributed Notes 3 notes