PHP的SPL标准库里的堆SplHeap怎么使用

[TOC]

PHP的SPL标准库里面的堆(SplHeap)怎么使用?

2019-10-12

一、总结:

1、因为SplHeap是抽象类,所以要先继承,实现里面的抽象方法compare后,才能new对象使用。

二、具体如何使用?

堆(Heap) 就是为了实现优先队列 而设计的一种数据结构,它是通过构造二叉树(二叉树的一种)实现。根节点最大的堆 叫做 最大堆或者大根堆,根节点最小的堆 叫做最小堆 或者 小根堆。二叉树还常用于排序(堆排序)。

如下:最小堆(任意节点的优先级不小于它的子节点)
最小堆

看看 PHP SplHeap 的实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// PHP手册-函数参考-其他基本扩展-SPL-数据结构
abstract SplHeap implements Iterator, Countable
{
/* 方法 */
public __construct ( void )
abstract protected compare (mixed $value1, mixed $value) : int
public count( void ) : int
public count ( void ) : int
public current ( void ) : mixed
public extract ( void ) : mixed
public insert ( mixed $value ) : void
public isCorrupted ( void ) : bool
public isEmpty ( void ) : bool
public key ( void ) : mixed
public next ( void ) : void
public recoverFromCorruption ( void ) : void
public rewind ( void ) : void
public top ( void ) : mixed
public valid ( void ) : bool
}

显然它是一个抽象类,最大堆(SplMaxHeap) 和最小堆(SplMinHeap) 就是继承它实现的。最大堆和最小堆并没有额外的方法。
SplHeap的简单使用如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class MySimpleHeap extends SplHeap
{
// compare()方法用来比较两个元素的大小,决定他们在堆中的位置
public function compare($value1, $value2)
{
// TODO: Implement compare() method.
//echo $value1;
//echo $value2;
return ($value1 - $value2);
}
}

$obj = new MySimpleHeap();
$obj->insert(4);
$obj->insert(8);
$obj->insert(1);
$obj->insert(0);

//echo $obj->top();// 8
//echo $obj->count();// 4

foreach ($obj as $number) {
echo $number;
}

三、参考手册

简介

The SplHeap class provides the main functionalities of a Heap.

类摘要

abstract SplHeap implements Iterator , Countable {

/* 方法 */

public [__construct](https://www.php.net/manual/zh/splheap.construct.php) ( void )

abstract protected [compare](https://www.php.net/manual/zh/splheap.compare.php) ( [mixed](https://www.php.net/manual/zh/language.pseudo-types.php#language.types.mixed) `$value1` , [mixed](https://www.php.net/manual/zh/language.pseudo-types.php#language.types.mixed) `$value2` ) : int

public [count](https://www.php.net/manual/zh/splheap.count.php) ( void ) : int

public [current](https://www.php.net/manual/zh/splheap.current.php) ( void ) : [mixed](https://www.php.net/manual/zh/language.pseudo-types.php#language.types.mixed)

public [extract](https://www.php.net/manual/zh/splheap.extract.php) ( void ) : [mixed](https://www.php.net/manual/zh/language.pseudo-types.php#language.types.mixed)

public [insert](https://www.php.net/manual/zh/splheap.insert.php) ( [mixed](https://www.php.net/manual/zh/language.pseudo-types.php#language.types.mixed) `$value` ) : void

public [isCorrupted](https://www.php.net/manual/zh/splheap.iscorrupted.php) ( void ) : bool

public [isEmpty](https://www.php.net/manual/zh/splheap.isempty.php) ( void ) : bool

public [key](https://www.php.net/manual/zh/splheap.key.php) ( void ) : [mixed](https://www.php.net/manual/zh/language.pseudo-types.php#language.types.mixed)

public [next](https://www.php.net/manual/zh/splheap.next.php) ( void ) : void

public [recoverFromCorruption](https://www.php.net/manual/zh/splheap.recoverfromcorruption.php) ( void ) : void

public [rewind](https://www.php.net/manual/zh/splheap.rewind.php) ( void ) : void

public [top](https://www.php.net/manual/zh/splheap.top.php) ( void ) : [mixed](https://www.php.net/manual/zh/language.pseudo-types.php#language.types.mixed)

public [valid](https://www.php.net/manual/zh/splheap.valid.php) ( void ) : bool

}

Table of Contents

实例1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
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.

实例2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
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)

四、测试题-简答题

1、优先队列的最主要作用是什么(两点)?

解答:a、实现优先队列 b、常用于排序(堆排序)

2、大根堆和小根堆的定义是什么?

解答:根节点最大的堆叫做最大堆或大根堆。

3、SplHeap是一个抽象类,那么我们要怎么使用它呢?

解答:继承,实现里面的抽象方法就可以使用了。

4、SplHeap里面的抽象方法有哪些?

解答:只有一个compare,abstract protected int compare ( mixed $value1 , mixed $value2 )

5、SplHeap里面的抽象方法compare方法怎么实现?

解答:就和普通方法的实现完全一样,因为会覆盖的。

1
public function compare($value1, $value2) {}

6、最大堆(SplMaxHeap)和最小堆(SplMinHeap)怎么实现的?

解答:最大堆(SplMaxHeap)和最小堆(SplMinHeap)就是继承SplHeap抽象类而实现的

7、我们应该怎么使用别人的类呢(从抽象类和普通类来说)?

解答:先看别人的类是不是抽象类,是的话我们要继承才能使用,还要注意实现里面的抽象方法,不是的话,直接new对象就好。

8、堆的英文怎么说,php中的标准库中的堆怎么写类名?

解答:Heap,驼峰命名法SplHeap,类首字母大写。

9、SplHeap的最常用三个方法是什么?

解答:insert(),top(),count()。

10、SplHeap的compare方法的返回值我们怎么写?

解答:

1
return ($value1 - $value2);

11、遍历堆的两种方法?

解答:foreach 和(valid()、current()、next())套件

12、PHP_EOF怎么使用?

解答:连接符.PHP_EOF

文章目录
  1. 1. PHP的SPL标准库里面的堆(SplHeap)怎么使用?
    1. 1.1. 一、总结:
    2. 1.2. 二、具体如何使用?
    3. 1.3. 三、参考手册
      1. 1.3.1. 简介
      2. 1.3.2. 类摘要
      3. 1.3.3. Table of Contents
      4. 1.3.4. 实例1
      5. 1.3.5. 实例2
    4. 1.4. 四、测试题-简答题
      1. 1.4.1. 1、优先队列的最主要作用是什么(两点)?
      2. 1.4.2. 2、大根堆和小根堆的定义是什么?
      3. 1.4.3. 3、SplHeap是一个抽象类,那么我们要怎么使用它呢?
      4. 1.4.4. 4、SplHeap里面的抽象方法有哪些?
      5. 1.4.5. 5、SplHeap里面的抽象方法compare方法怎么实现?
      6. 1.4.6. 6、最大堆(SplMaxHeap)和最小堆(SplMinHeap)怎么实现的?
      7. 1.4.7. 7、我们应该怎么使用别人的类呢(从抽象类和普通类来说)?
      8. 1.4.8. 8、堆的英文怎么说,php中的标准库中的堆怎么写类名?
      9. 1.4.9. 9、SplHeap的最常用三个方法是什么?
      10. 1.4.10. 10、SplHeap的compare方法的返回值我们怎么写?
      11. 1.4.11. 11、遍历堆的两种方法?
      12. 1.4.12. 12、PHP_EOF怎么使用?
本站总访问量 | 本页面被访问 | 您是第位小伙伴

© XueSi博客 版权所有 备案号 : 赣ICP备19008485号-1