PHP プライオリティ キューの概要 (コード付き)

この記事では、PHP プライオリティ キューの概要 (コード付き) を紹介します。一定の参考価値があります。必要な友人は参照してください。お役に立てば幸いです。

PHP の SPL ライブラリには SplPriorityQueue 優先キューが組み込まれており、ヒープ データ構造で実装されています。デフォルトは MaxHeap モードです。つまり、優先度が大きいほどキューに優先順位が与えられます。同時に、compareメソッドを書き換えることでMinHeapを利用することも可能です（優先度が低いほどデキューが優先され、シナリオは非常に少ないようです）。

SplPriorityQueue

ヒープの特性

ここで注意して理解する必要があります: SplPriorityQueue はヒープ データ構造で実装されています。デキューするときは、次の場所にある要素を取り出します。このとき、ヒープの特性は破壊され、ヒープは安定した状態 (MaxHeap または MinHeap) に応じて調整されます。つまり、最後の要素がヒープの先頭に置き換えられます。ヒープの特性を満たしていない場合は、調整を続けるか、安定したヒープが得られるため、優先度が同じ場合、デキューの順序はエンキューに続きません。注文。

ソースコード例:

<?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

5つのタスクの優先度は同じですが、キューの特性上、キューに参加した順にデータが返されるわけではないことがわかります。ヒープ:
1 、task1、task2、task3、task4、task5 がキューに登録されており、優先順位が同じであるため、ヒープは常に安定した状態になります。
2. デキューしてタスク 1 を取得すると、ヒープはまず構造をタスク 5、タスク 2、タスク 3、タスク 4 に調整し、安定した状態に達します。
3. デキューしてタスク 5 を取得すると、ヒープはまず構造をタスク 4、タスク 2、タスク 3 に調整し、安定した状態に達します。
4. デキューしてタスク 4 を取得すると、ヒープはまず構造をタスク 3、タスク 2 に調整し、安定した状態に達します。
5. デキューしてタスク 3 を取得します。ヒープはまず構造をタスク 2 に調整し、安定した状態に達します。
4. チームを離れ、タスク 2 を取得します。

Iterator, Countable

SplPriorityQueue は Iterator, Countable インターフェイスを実装しているため、foreach/count 関数で操作したり、rewind、valid、current、next/count メソッドを使用したりできます。

これはヒープ実装であるため、rewind メソッドは効果のない no-op 操作であることに注意してください。これは、ヘッド ポインターが常にヒープの先頭を指しているためです。つまり、current は常に次と等しいためです。単にさまようポインタである List とは異なり、top キューはヒープ要素を削除します (extract = current next (current はデキューされ、ヒープから削除されます))。

<?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 デキューはよりフレンドリーです。つまり、最も高い優先順位を持つ要素が常に返されます。優先順位が一貫している場合、データは次のようになります。ヒープ調整機能を使用して返されます。

<?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;
}

カスタム優先度処理メソッド

比較メソッドをオーバーライドして、独自の優先度処理メカニズムを定義します。

<?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());
}

この記事はここで終了しました。さらにエキサイティングなコンテンツについては、PHP 中国語 Web サイトの PHP ビデオ チュートリアル 列に注目してください。

以上がPHP プライオリティ キューの概要 (コード付き)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。