PHPのPriorityQueueの実装についてとSplPriorityQueueの使い方

JavaやC++だとPriorityQueueが標準ライブラリで用意されているイメージがありますが、PHPはあまりそういったイメージがありません。しかし、PHPでもちゃんとPriorityQueueが標準で用意されています。

SplPriorityQueue の使い方

PHPのPriorityQueueの実装がSplPriorityQueueです。その基本的な使い方は以下の通りです。

<?php

$queue = new SplPriorityQueue();

// insert メソッドで要素を挿入
// $queue->insert(<挿入するオブジェクト>, <そのオブジェクトのPriority>); 
$queue->insert('Hoge', 1);
$queue->insert('Fuga', 3);
$queue->insert('Piyo', 2);

// isEmpty() でqueueが空かどうかを判断
while(!$queue->isEmpty()) {
    // extractは先頭の要素を取り出しつつその要素をqueueから削除
    var_dump($queue->extract());
}

これの実行結果は以下のようになります。

string(4) "Fuga"
string(4) "Piyo"
string(4) "Hoge"

Queueの中から、Priorityが高い順に取り出されていることがわかります。

主なメソッドは以下の通りです。

• insert() : Queueに要素そ挿入
• isEmpty() : Queueが空ならtrue
• extract() : Queueの先頭の要素を取り出しつつその要素をQueueから削除
• top() : Queueの先頭の要素を取り出す。Queueからの削除は行わない
• count() : Queueの中身の数を取得

発展 - 優先度が低い順に取り出したりする時は...？

SplPriorityQueueのデフォルトの実装では、優先度が高い順に要素を取り出すようになっていますが、優先度が低い順に取り出したかったり、優先度を複雑に設定したかったりする場合があると思います。

優先度が低い順に取り出したい

SplPriorityQueue を継承したクラスを作り、compare メソッドをオーバーロードすることで可能となります。

<?php

class MyPriorityQueue extends SplPriorityQueue {
    /** Queueの中身を昇順でソートするように変更 */
    public function compare($priority1, $priority2) {
        if($priority1 === $priority2) return 0;
        $priority1 < $priority2 ? -1 : 1;
    }
}

$queue = new MyPriorityQueue();

$queue->insert('Hoge', 1);
$queue->insert('Fuga', 3);
$queue->insert('Piyo', 2);

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

こうすることで結果は以下のようになり、昇順で取り出されるようになります。

string(4) "Hoge"
string(4) "Piyo"
string(4) "Fuga"

パーフェクトPHP (PERFECT SERIES 3)