SplPriorityQueue（堆之优先队列） · PHP学习

# SplPriorityQueue（堆之优先队列） ## [SplPriorityQueue:优先队列](https://www.php.net/manual/zh/class.splpriorityqueue.php#class.splpriorityqueue) > 优先队列也是非常实用的一种数据结构，可以通过加权对值进行排序，由于排序在php内部实现，业务代码中将精简不少而且更高效。通过SplPriorityQueue::setExtractFlags(int $flag)设置提取方式可以提取数据（等同最大堆）、优先级、和两者都提取的方式 > SplPriorityQueue类提供了使用最大堆实现的优先级队列的主要功能。注意：具有相同优先级的元素的顺序未定义。它可能与插入顺序不同 > SplPriorityQueue是以`Heap`：`堆`数据结构实现的，默认为`MaxHeap`模式，即`priority`越大越优先出队，同时可以通过重写`compare`方法来使用`MinHeap`（优先级越低越优先出队，场景貌似很少吧） > 理解：当我们出队时会拿出`堆顶`的元素，此时`堆`的特性被破坏，`堆`会进行相应的调整至`稳定态`(`MaxHeap`or`MinHeap`)，即会将`最后`一个元素替换到`堆顶`，然后进行`稳定态`验证，不符合堆特性则继续调整，或者我们就得到了一个`稳定态`的`堆`，所以当优先级相同，出队顺序并不会按照入队顺序 > SplPriorityQueue的入队方法和出队方法：insert和extract > extract 出队更为友好，即始终返回优先级最高的元素，优先级相投时会以堆调整的特性返回数据 > 注意，因为是`堆`实现，所以`rewind`方法是一个`no-op`没有什作用的操作，因为`头指针`始终指向`堆顶`，即`current`始终等于`top`，不像`List`只是游走指针，出队是会删除堆元素的，`extract`=`current + next`（current出队，从堆中删除） ``` <pre class="calibre10">``` abstract SplHeap implements Iterator , Countable { /* 方法 */ public __construct ( void ) abstract protected compare ( mixed $value1 , mixed $value2 ) : int //比较元素，以便在筛选时将它们正确地放在堆中，如果value1大于value2则为正整数，如果相等则为0，否则为负整数 public count ( void ) : int //返回元素的个数 Countable public current ( void ) : mixed //返回当前记录节点索引的值超出范围返回空 Iterator public extract ( void ) : mixed //从堆顶部提取节点并进行筛选 public insert ( mixed $value ) : void //通过筛选将一个元素插入堆中 public isCorrupted ( void ) : bool //判断堆是否处于损坏状态 public isEmpty ( void ) : bool //检查堆是否为空 public key ( void ) : mixed //返回当前节点索引 Iterator public next ( void ) : void //移动到下一个节点 Iterator public recoverFromCorruption ( void ) : void //从损坏的状态恢复并允许堆上的进一步操作 public rewind ( void ) : void //将指针指向迭代开始处 Iterator public setExtractFlags ( int $flags ) : void //设置提取模式 public top ( void ) : mixed //返回堆顶部的节点 public valid ( void ) : bool //检查堆是否还有节点 Iterator } ``` ``` ## **例子：** ``` <pre class="calibre10">``` <?php $objPQ = new SplPriorityQueue(); $objPQ->insert('A',3); $objPQ->insert('B',6); $objPQ->insert('C',1); $objPQ->insert('D',2); echo "COUNT->".$objPQ->count()." "; //mode of extraction /** * 设置元素出队模式 * SplPriorityQueue::EXTR_DATA 仅提取值 * SplPriorityQueue::EXTR_PRIORITY 仅提取优先级 * SplPriorityQueue::EXTR_BOTH 提取数组包含值和优先级 */ $objPQ->setExtractFlags(SplPriorityQueue::EXTR_BOTH); //Go to TOP $objPQ->top(); //遍历： while($objPQ->valid()){ print_r($objPQ->current()); echo " "; $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 ) ?> ``` ``` ## **例子：** ``` <pre class="calibre17">``` <?php class PQtest extends SplPriorityQueue { public function compare($priority1, $priority2) { //$priority1与优先级相同 3 6 ... if ($priority1 === $priority2) return 0; return $priority1 < $priority2 ? -1 : 1; // return $priority1 - $priority2;//高优先级优先 // return $priority2 - $priority1;//低优先级优先 } } $objPQ = new PQtest(); //$objPQ->insert('值',优先级); $objPQ->insert('A',3); $objPQ->insert('B',6); $objPQ->insert('C',1); $objPQ->insert('D',2); echo "COUNT->".$objPQ->count()." "; /** * 设置元素出队模式 * SplPriorityQueue::EXTR_DATA 仅提取值 * SplPriorityQueue::EXTR_PRIORITY 仅提取优先级 * SplPriorityQueue::EXTR_BOTH 提取数组包含值和优先级 */ $objPQ->setExtractFlags(PQtest::EXTR_BOTH); //Go to TOP $objPQ->top(); while($objPQ->valid()){ print_r($objPQ->current()); echo " "; $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 ) ``` ```