PHP Conference Japan 2024

SplHeap 类

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

介绍

SplHeap 类提供了堆的主要功能。

类概要

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): true
public isCorrupted(): bool
public isEmpty(): bool
public key(): int
public next(): void
public rewind(): void
public top(): mixed
public valid(): bool
}

目录

添加注释

用户贡献注释 3 条注释

Michelangelo van Dam
15 年前
为了更好地了解 SplHeap 的用途,我创建了一个小的示例脚本,它将显示比利时足球队在朱比勒联赛中的排名。

<?php
/**
* 扩展 SplHeap 类,用于显示比利时足球联赛 JupilerLeague 的排名
*/
class JupilerLeague extends SplHeap
{
/**
* 我们修改抽象方法 compare,以便可以使用给定数组的值对我们的排名进行排序
*/
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;
}
}

// 让我们在这里填充堆 (2009 年的数据)
$heap = new JupilerLeague();
$heap->insert(array ('AA Gent' => 15));
$heap->insert(array ('安德莱赫特' => 20));
$heap->insert(array ('布鲁日足球俱乐部' => 11));
$heap->insert(array ('沙勒罗瓦' => 12));
$heap->insert(array ('布鲁日俱乐部' => 21));
$heap->insert(array ('比尔肖特' => 15));
$heap->insert(array ('科尔特赖克' => 10));
$heap->insert(array ('梅赫伦' => 18));
$heap->insert(array ('洛克伦' => 10));
$heap->insert(array ('莫斯科罗恩' => 7));
$heap->insert(array ('亨克' => 11));
$heap->insert(array ('鲁瑟拉尔' => 6));
$heap->insert(array ('标准列日' => 20));
$heap->insert(array ('圣特鲁伊登' => 17));
$heap->insert(array ('韦斯特洛' => 10));
$heap->insert(array ('瓦雷格姆' => 15));

// 为了显示排名,我们移动到第一个节点
$heap->top();

// 然后我们迭代每个节点以显示结果
while ($heap->valid()) {
list (
$team, $score) = each ($heap->current());
echo
$team . ': ' . $score . PHP_EOL;
$heap->next();
}
?>

这将产生以下输出
布鲁日俱乐部: 21
安德莱赫特: 20
标准列日: 20
梅赫伦: 18
圣特鲁伊登: 17
瓦雷格姆: 15
AA 根特: 15
比尔肖特: 15
沙勒罗瓦: 12
亨克: 11
布鲁日足球俱乐部: 11
科尔特赖克: 10
洛克伦: 10
韦斯特洛: 10
莫斯科罗恩: 7
鲁瑟拉尔: 6

希望这个例子为 SplHeap 的更复杂实现铺平了道路。
igorsantos07 at gmail dot com
10 年前
虽然 Michelangelo Van Dam 的例子 (http://br2.php.net/manual/en/class.splheap.php#93930) 很好地展示了 SplHeap 的功能,但这个实现与 SplPriorityQueue 的功能完全相同——基于 SplMaxHeap。如果你打算复制这段代码片段,那就不要再继续了!有一个 SPL 类可以完全满足你的需求 :)
Anthony
8 年前
如果你想构建一个真正的基于树的堆,你可以按照如下方式进行(使用 SplMinHeap 实现,但如果希望按相反的顺序排列项目,也可以使用 SplMaxHeap)

我们试图表示的结构

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

<?php
$h
= new SplMinHeap();

// [父节点, 子节点]
$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";
}
?>

当你迭代堆时,返回的数据将像阅读书籍一样读取;即从左到右,从上到下。它不会遵循这些关系。

因此,上面的代码将输出以下内容

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