PHPで優先度つきキュー

  • 35
    いいね
  • 0
    コメント
この記事は最終更新日から1年以上が経過しています。

PHP5.3でSplPriorityQueue、優先度つきキューが実装されました。
取得時、第二引数の値が高いものから順に並べ替えられます。
データの種類によっては、自力でソートする必要が無くなります。

<?php

    $queue = new SplPriorityQueue();

    $queue->insert('低い', 10);
    $queue->insert('最優先', 100);
    $queue->insert('にばんめその1', 50);
    $queue->insert('にばんめその2', 50);
    $queue->insert('一番低い', 1);

    // 個数 → 5
    print('件数:' . $queue->count());

    // 一番目を閲覧。これは使っても無くならない。
    print('一番目:' . $queue->top());

    // 優先順位の高い順に取り出す
    foreach($queue as $key=>$val){
        print('キー:' . $key . ' 値:' . $val);
    }

    // 一度使うと無くなる → 0
    print('件数:' . $queue->count());

    // rewindは意味がない
    $queue->rewind();

出力

    件数:5
    一番目:最優先
    キー:5 値:最優先
    キー:4 値:にばんめその2
    キー:3 値:にばんめその1
    キー:2 値:低い
    キー:1 値:一番低い
    件数:0

優先したいデータから順に表示することができました。
なお、同じ優先度内での順番がどうなるかは保証されていません。

実用としてはわりと困ることに、Wikipediaの定義通りの実装がなされています。
どういうことって一度使ったら無くなってしまうんですよね。
具体的にはSplPriorityQueue::next()したときに、イテレータを進めるかわりにshiftするので値が消滅します。

なので繰り返し使う場合はcloneするか、配列に取り出すなどしてから扱う必要があります。