php标准库中的优先队列SplPriorityQueue怎么使用？（继承）
一、总结
1、new对象，然后通过insert方法和extract方法来使用，top方法也很常用。
2、类的话首先想到继承，所以可以继承SplPriorityQueue来实现自己特定功能的优先队列。（继承思想）
二、php标准库中的优先队列SplPriorityQueue怎么使用？
而优先队列SplPriorityQueue是基于堆(后文介绍)实现的。
SplPriorityQueue简单使用：
$pq = new SplPriorityQueue();
$pq->insert('a', 10);
$pq->insert('b', 1);
$pq->insert('c', 8);
echo $pq->count() .PHP_EOL; //
echo $pq->current() . PHP_EOL; //a
/**
* 设置元素出队模式
* SplPriorityQueue::EXTR_DATA 仅提取值
* SplPriorityQueue::EXTR_PRIORITY 仅提取优先级
* SplPriorityQueue::EXTR_BOTH 提取数组包含值和优先级
*/
$pq->setExtractFlags(SplPriorityQueue::EXTR_DATA);
while($pq->valid()) {
print_r($pq->current()); //a c b
$pq->next();
}
三、php手册：SplPriorityQueue
简介¶
The SplPriorityQueue class provides the main functionalities of a prioritized queue, implemented using a max heap.
类摘要¶
SplPriorityQueue implements Iterator , Countable {
/* 方法 */
public __construct ( void )
public int count ( void )
public mixed current ( void )
public mixed extract ( void )
public int getExtractFlags ( void )
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 void setExtractFlags ( int
$flags )public mixed top ( void )
public bool valid ( void )
}
Table of Contents¶
- SplPriorityQueue::compare — Compare priorities in order to place elements correctly in the heap while sifting up
- SplPriorityQueue::__construct — Constructs a new empty queue
- SplPriorityQueue::count — Counts the number of elements in the queue
- SplPriorityQueue::current — Return current node pointed by the iterator
- SplPriorityQueue::extract — Extracts a node from top of the heap and shift up
- SplPriorityQueue::getExtractFlags — Get the flags of extraction
- SplPriorityQueue::insert — Inserts an element in the queue by sifting it up
- SplPriorityQueue::isCorrupted — Tells if the priority queue is in a corrupted state
- SplPriorityQueue::isEmpty — Checks whether the queue is empty
- SplPriorityQueue::key — Return current node index
- SplPriorityQueue::next — Move to the next node
- SplPriorityQueue::recoverFromCorruption — Recover from the corrupted state and allow further actions on the queue
- SplPriorityQueue::rewind — Rewind iterator back to the start (no-op)
- SplPriorityQueue::setExtractFlags — Sets the mode of extraction
- SplPriorityQueue::top — Peeks at the node from the top of the queue
- SplPriorityQueue::valid — Check whether the queue contains more nodes
quick implementation of SPL Priority Queue: <?php class PQtest extends SplPriorityQueue
{
public function compare($priority1, $priority2)
{
if ($priority1 === $priority2) return 0;
return $priority1 < $priority2 ? -1 : 1;
}
} $objPQ = new PQtest(); $objPQ->insert('A',3);
$objPQ->insert('B',6);
$objPQ->insert('C',1);
$objPQ->insert('D',2); echo "COUNT->".$objPQ->count()."<BR>"; //mode of extraction
$objPQ->setExtractFlags(PQtest::EXTR_BOTH); //Go to TOP
$objPQ->top(); while($objPQ->valid()){
print_r($objPQ->current());
echo "<BR>";
$objPQ->next();
} ?> output: COUNT->4
Array ( [data] => B [priority] => 6 )
Array ( [data] => A [priority] => 3 )
Array ( [data] => D [priority] => 2 )
Array ( [data] => C [priority] => 1 )
四、测试题-简答题
1、SplPriorityQueue的入队方法和出队方法是什么？
解答：insert和extract。top方法也很常用。
2、如何遍历一个SplPriorityQueue？
解答：valid()+current()+next()。
29 while($objPQ->valid()){
30 print_r($objPQ->current());
31 echo "<BR>";
32 $objPQ->next();
33 }
3、SplPriorityQueue的实现原理是什么，用的那种数组结构？
解答：用的大根堆。using a max heap。
4、如何插入一个元素到SplPriorityQueue中去？
解答：$objPQ->insert('A',3); 先值后优先级，是一个map。
5、如何写符合自己功能的优先队列（通过继承）？（有类先想继承）
解答：继承SplPriorityQueue类即可，class PQtest extends SplPriorityQueue 。
6、如何设置SplPriorityQueue的提取数据方式，是值是优先级还是两者都提取？
解答：通过SPLPriorityQueue的setExtractFlags方法，$pq->setExtractFlags(SplPriorityQueue::EXTR_DATA);