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

一、总结

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

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

堆(Heap)就是为了实现优先队列而设计的一种数据结构，它是通过构造二叉堆(二叉树的一种)实现。根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。二叉堆还常用于排序(堆排序)。
如下：最小堆（任意节点的优先级不小于它的子节点）

看看PHP SplHeap的实现：

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

class MySimpleHeap extends SplHeap 
{ 
  //compare()方法用来比较两个元素的大小，绝对他们在堆中的位置 
  public function compare( $value1, $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; 
}

三、参考手册SplHeap

简介 ¶

The SplHeap class provides the main functionalities of a Heap.

类摘要 ¶

abstract SplHeap implements Iterator , Countable {

/* 方法 */

public __construct ( void )

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

public int count ( void )

public mixed current ( void )

public mixed extract ( void )

public void insert ( mixed $value )

public bool isCorrupted ( void )

public bool isEmpty ( void )

public mixed key ( void )

public void next ( void )

public void recoverFromCorruption ( void )

public void rewind ( void )

public mixed top ( void )

public bool valid ( void )

}

Table of Contents ¶

SplHeap::compare — Compare elements in order to place them correctly in the heap while sifting up
SplHeap::__construct — Constructs a new empty heap
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

实例

 1 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.
 2 
 3 <?php
 4 /**
 5 * A class that extends SplHeap for showing rankings in the Belgian
 6 * soccer tournament JupilerLeague
 7 */
 8 class JupilerLeague extends SplHeap 
 9 {
10     /**
11      * We modify the abstract method compare so we can sort our
12      * rankings using the values of a given array
13      */
14     public function compare($array1, $array2)
15     {
16         $values1 = array_values($array1);
17         $values2 = array_values($array2);
18         if ($values1[0] === $values2[0]) return 0;
19         return $values1[0] < $values2[0] ? -1 : 1;
20     }
21 }
22 
23 // Let's populate our heap here (data of 2009)
24 $heap = new JupilerLeague();
25 $heap->insert(array ('AA Gent' => 15));
26 $heap->insert(array ('Anderlecht' => 20));
27 $heap->insert(array ('Cercle Brugge' => 11));
28 $heap->insert(array ('Charleroi' => 12));
29 $heap->insert(array ('Club Brugge' => 21));
30 $heap->insert(array ('G. Beerschot' => 15));
31 $heap->insert(array ('Kortrijk' => 10));
32 $heap->insert(array ('KV Mechelen' => 18));
33 $heap->insert(array ('Lokeren' => 10));
34 $heap->insert(array ('Moeskroen' => 7));
35 $heap->insert(array ('Racing Genk' => 11));
36 $heap->insert(array ('Roeselare' => 6));
37 $heap->insert(array ('Standard' => 20));
38 $heap->insert(array ('STVV' => 17));
39 $heap->insert(array ('Westerlo' => 10));
40 $heap->insert(array ('Zulte Waregem' => 15));
41 
42 // For displaying the ranking we move up to the first node
43 $heap->top();
44 
45 // Then we iterate through each node for displaying the result
46 while ($heap->valid()) {
47   list ($team, $score) = each ($heap->current());
48   echo $team . ': ' . $score . PHP_EOL;
49   $heap->next();
50 }
51 ?>
52 
53 This results in the following output:
54 Club Brugge: 21
55 Anderlecht: 20
56 Standard: 20
57 KV Mechelen: 18
58 STVV: 17
59 Zulte Waregem: 15
60 AA Gent: 15
61 G. Beerschot: 15
62 Charleroi: 12
63 Racing Genk: 11
64 Cercle Brugge: 11
65 Kortrijk: 10
66 Lokeren: 10
67 Westerlo: 10
68 Moeskroen: 7
69 Roeselare: 6
70 
71 Hope this example paved the way for more complex implementations of SplHeap.

四、测试题-简答题

1、优先队列的最主要作用是什么（两点）？

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

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

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

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

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

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

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

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

解答：就和普通方法的实现完全一样，因为会覆盖的。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方法的返回值我们怎么写？

解答：return ( $value1 - $value2 );

11、遍历堆的两种方法？

解答：foreach 和（valid()、current()、next()）套件

12、PHP_EOF怎么使用？

解答：连接符.PHP_EOF