PHP

PHPで優先度つきキュー

More than 5 years have passed since last update.

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するか、配列に取り出すなどしてから扱う必要があります。