Introduction to PHP priority queue (with code)

This article brings you an introduction to PHP priority queue (with code). It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

PHP's SPL library has a built-in SplPriorityQueue priority queue, and it is implemented with the Heap data structure. The default is MaxHeap mode, that is, the larger the priority, the priority is given to the queue. At the same time, MinHeap can be used by rewriting the compare method ( The lower the priority, the more priority is given to dequeuing, there seems to be very few scenarios).

SplPriorityQueue

Heap characteristics

You need to pay attention and understand here: SplPriorityQueue is implemented with a heap data structure. When we dequeue, we will take out the elements at the top of the heap. At this time, the characteristics of the heap are destroyed, and the heap will be adjusted accordingly to the stable state (MaxHeap or MinHeap), that is, the last element will be replaced on the top of the heap, and then the stable state verification will be performed. If it does not meet the characteristics of the heap, continue to adjust, or we A stable heap is obtained, so when the priorities are the same, the dequeuing order will not follow the enqueuing order.

Source code example:

<?php $splPriorityQueue = new \SplPriorityQueue();
// 设定返回数据的meta信息
// \SplPriorityQueue::EXTR_DATA 默认 只返回数
// \SplPriorityQueue::EXTR_PRIORITY 只返回优先级
// \SplPriorityQueue::EXTR_BOTH 返回数据和优先级
// $splPriorityQueue->setExtractFlags(\SplPriorityQueue::EXTR_DATA);
$splPriorityQueue->insert("task1", 1);
$splPriorityQueue->insert("task2", 1);
$splPriorityQueue->insert("task3", 1);
$splPriorityQueue->insert("task4", 1);
$splPriorityQueue->insert("task5", 1);

echo $splPriorityQueue->extract() . PHP_EOL;
echo $splPriorityQueue->extract() . PHP_EOL;
echo $splPriorityQueue->extract() . PHP_EOL;
echo $splPriorityQueue->extract() . PHP_EOL;
echo $splPriorityQueue->extract() . PHP_EOL;

//执行结果
task1
task5
task4
task3
task2

It can be seen that although the five tasks have the same priority, the queue does not return data in the order of joining the queue, because of the characteristics of the heap:
1 , task1, task2, task3, task4, task5 are queued. Because the priorities are the same, the heap is always in a stable state.
2. Dequeue, get task1, the heap first adjusts the structure to task5, task2, task3, task4, and has reached a stable state.
3. Dequeue, get task5, the heap first adjusts the structure to task4, task2, task3, and has reached a stable state.
4. Dequeue, get task4, the heap first adjusts the structure to task3, task2, and has reached a stable state.
5. Dequeue and get task3. The heap first adjusts the structure to task2 and has reached a stable state.
4. Leave the team and get task2.

Iterator, Countable

SplPriorityQueue implements the Iterator, Countable interface, so we can operate it with the foreach/count function, or use the rewind, valid, current, next/count method.

Note that because it is a heap implementation, the rewind method is a no-op operation that has no effect, because the head pointer always points to the top of the heap, that is, current is always equal to top, unlike List, which is just a wandering pointer. The queue will delete the heap elements, extract = current next (current is dequeued and deleted from the heap).

<?php $splPriorityQueue = new \SplPriorityQueue();

$splPriorityQueue->insert("task1", 1);
$splPriorityQueue->insert("task2", 2);
$splPriorityQueue->insert("task3", 1);
$splPriorityQueue->insert("task4", 4);
$splPriorityQueue->insert("task5", 5);

echo "Countable： " . count($splPriorityQueue) . PHP_EOL;

// 迭代的话会删除队列元素 current 指针始终指向 top 所以 rewind 没什么意义
for ($splPriorityQueue->rewind(); $splPriorityQueue->valid();$splPriorityQueue->next()) { 
    var_dump($splPriorityQueue->current());
    var_dump($splPriorityQueue->count());
    $splPriorityQueue->rewind();
}

var_dump("is empty:" . $splPriorityQueue->isEmpty());

Extract dequeue

extract Dequeue is more friendly, that is, the element with the highest priority is always returned. When the priorities are consistent, the data will be returned with the heap adjustment feature. .

<?php $splPriorityQueue = new \SplPriorityQueue();

// data  priority
$splPriorityQueue->insert("task1", 1);
$splPriorityQueue->insert("task2", 2);
$splPriorityQueue->insert("task3", 1);
$splPriorityQueue->insert("task4", 4);
$splPriorityQueue->insert("task5", 5);

echo "Countable： " . count($splPriorityQueue) . PHP_EOL;

while (! $splPriorityQueue->isEmpty()) {
    var_dump($splPriorityQueue->extract());
    echo $splPriorityQueue->count() . PHP_EOL;
}

Custom priority processing method

Override the compare method to define your own priority processing mechanism.

<?php class CustomedSplPriorityQueue extends SplPriorityQueue
{
    public function compare($priority1, $priority2): int
    {
        // return $priority1 - $priority2;//高优先级优先
        return $priority2 - $priority1;//低优先级优先
    }
}

$splPriorityQueue = new \CustomedSplPriorityQueue();
$splPriorityQueue->setExtractFlags(SplPriorityQueue::EXTR_BOTH);
$splPriorityQueue->insert("task1", 1);
$splPriorityQueue->insert("task2", 2);
$splPriorityQueue->insert("task3", 1);
$splPriorityQueue->insert("task4", 4);
$splPriorityQueue->insert("task5", 5);
 
echo "Countable： " . count($splPriorityQueue) . PHP_EOL;

while (!$splPriorityQueue->isEmpty()) {
    var_dump($splPriorityQueue->extract());
}

This article has ended here. For more exciting content, you can pay attention to the PHP Video Tutorial column on the PHP Chinese website!

The above is the detailed content of Introduction to PHP priority queue (with code). For more information, please follow other related articles on the PHP Chinese website!