[PHP] ヒープを使う(SplHeap)

PHPでヒープを使おうと思ったんですが、
マニュアル(php.net)の説明が少ないので、
いろいろ試してみたことを書きます。

ヒープ(プライオリティキュー)とは

ざっくりとした理解です。

最小/最大値の要素が根となる二分木(=ヒープ)を利用して、
効率よく最小/最大値を取り出すデータ構造。

要素を追加、取り出しする度に、
最小/最大値が根となるよう整列し、
その際に整列するための計算量は、O(log N)となる。

これを通常の配列で最小/最大値を検索しようとすると、
線形探索で、計算量はO(N)となる。

ちなみに、log N っていうのは、
10を何乗すればNになるか。を表す数値で、
　N = 10 の時、log N = 1
　N = 100 の時、log N = 2
　N = 1000 の時、log N = 3
　…
となり、

計算量を、O(N)からO(log N)に落とすと、
Nが大きくなればなるほど、
絶大に効いてくるのがわかります。

クラスの種類

とりあえず、この3つ使ってみました。
・SplMaxHeap (最大値を根として取り出す)
・SplMinHeap (最小値を根として取り出す)
・SplPriorityQueue (別途指定する優先度順)

※SplHeap自体は抽象クラスのため、インスタンス化不可

要素の追加(insert)

要素を追加するメソッド。

insert($val);
    $heap = get_private_array(print_r($que, true), $property);
    print('insert: ' . $val . ', heap: [' . implode(', ', $heap) . "]\n");
}

====== 出力 =======
insert: 1, heap: [1]
insert: 2, heap: [2, 1]
insert: 3, heap: [3, 1, 2]
insert: 4, heap: [4, 3, 2, 1]
insert: 5, heap: [5, 4, 2, 1, 3]

※get_private_arrayは、privateのプロパティを配列として返す自作関数。
　ここでは、SplMaxHeap内のheapプロパティ(private)を取得。
　詳細は前の記事へ。

追加するごとに、適宜並び替えられてます。

このリストをヒープに置き換えてみると、

こんな順番になるように並べられているようです。
(○の中の数字は、リストのindex。)

SplPriorityQueueの場合は、優先度を指定する。

$array = range(1, 5);
$que = new SplPriorityQueue();

for ($i = 0; $i < 5; $i++) {
    $que->insert($array[$i], $i);
}
print_r($que);

====== 出力 =======
SplPriorityQueue Object
(
    [flags:SplPriorityQueue:private] => 1
    [isCorrupted:SplPriorityQueue:private] => 
    [heap:SplPriorityQueue:private] => Array
        (
            [0] => Array
                (
                    [data] => 5
                    [priority] => 4
                )

            [1] => Array
                (
                    [data] => 4
                    [priority] => 3
                )

            [2] => Array
              <以下略>
        )

)

※get_private_arrayは2次元配列に非対応ｗ

要素の取り出し(extract)

最大値/最小値(優先度が最大の値)を取り出す。
取り出すとその要素はヒープからなくなり、
ヒープは新たに整列される。

($que->heap == [5, 4, 2, 1, 3]の状態)

while ($que->count() > 0){
    $val = $que->extract();
    $heap = get_private_array(print_r($que, true), $property);
    print('extract: ' . $val . ', heap: [' . implode(', ', $heap) . "]\n");
}

====== 出力 =======
extract: 5, heap: [4, 3, 2, 1]
extract: 4, heap: [3, 1, 2]
extract: 3, heap: [2, 1]
extract: 2, heap: [1]
extract: 1, heap: []

一方、topメソッドは、優先度が最大の要素を取り出すが、
取り出した要素はなくならない。

($que->heap == [5, 4, 2, 1, 3]の状態)

$val = $que->top();
$heap = get_private_array(print_r($que, true), $property);
print('top: ' . $val . ', heap: [' . implode(', ', $heap) . "]\n");

====== 出力 =======
top: 5, heap: [5, 4, 2, 1, 3]　←変わってない

ヒープに格納された要素を順に取り出したい場合は、
extractを使うといい。

要素があるかどうか、空かどうか(valid、isEmpty)

　・valid : heapに要素があればTrue、空ならFalseを返す。
　・isEmpty : heapが空ならTrue、そうでなければFalseを返す。

これらを使うと、例えば↑↑のextractのコードは、
次のように書き換えられる。

($que->heap == [5, 4, 2, 1, 3]の状態)

// validを使う
while ($que->valid()){
    $val = $que->extract();
    $heap = get_private_array(print_r($que, true), $property);
    print('extract: ' . $val . ', heap: [' . implode(', ', $heap) . "]\n");
}

// isEmptyを使う
while (true){
    if ($que->isEmpty()) break;
    <以下同文>
}

取り出しのタイプを設定(setExtractFlags)

SplPriorityQueueでは、取り出す要素(値か優先度か)を変更できる。
参考：SplPriorityQueue::setExtractFlags

flagsを設定することで、
extractの時に取り出す値を指定する。

値と優先度を一緒に取り出すには、
例えばこのように書く。

$array = range(1, 5);
$que = new SplPriorityQueue();

for ($i = 0; $i < 5; $i++) {
    $que->insert($array[$i], $i);
}

$que->setExtractFlags(3);
while ($que->valid()){
    list('data' => $data, 'priority' => $priority) = $que->extract();
    print('data: ' . $data . ', priority: ' . $priority . "\n");
}

====== 出力 =======
data: 5, priority: 4
data: 4, priority: 3
data: 3, priority: 2
data: 2, priority: 1
data: 1, priority: 0

以上