SplMinHeapのデータを再構築 : PHP

Tweet

Pocket

格納順序によらず、常に最小値のデータが取り出されるようなデータ構造をヒープと呼びます。PHPは、SplMinHeapを継承してcompareメソッドを実装するだけでヒープを実現できます。SplMinHeapを使ってみて、気になった点をメモします。

例ではオブジェクトの大小を以下の基準で定義しています。

1. elementsプロパティ（配列）の要素数
2. elementsプロパティの要素数が同じときはidプロパティ

<?php
class MyHeap extends \SplMinHeap
{
    public function compare($o1, $o2)
    {
        return count($o2->elements) <=> count($o1->elements) ?: $o2->id <=> $o1->id;
    }
}

SplMinHeapは、insert()が実行されたときのみcompare()が実行されて、データが構築されます。
以下の例では、(1)でelementsプロパティに要素が追加されても、データは再構築されず、current()は追加前と同じオブジェクトを返します。

$obj1           = new \StdClass();
$obj1->id       = 1;
$obj1->elements = ['a', 'b', 'c', 'd', 'e'];

$obj2           = new \StdClass();
$obj2->id       = 2;
$obj2->elements = ['a', 'b'];

$obj3           = new \StdClass();
$obj3->id       = 3;
$obj3->elements = ['a', 'b', 'c'];

$heap = new MyHeap();
$heap->insert($obj1);
$heap->insert($obj2);
$heap->insert($obj3);

$o = $heap->current();
var_dump($o->id); // 2

$obj2->elements[] = 'c'; // --- (1)
$obj2->elements[] = 'd';

$o = $heap->current();
var_dump($o->id); // 2   // --- (2)

そこで、再構築用にrebuild()を定義して実行することで、最小値を取り出すことにしました。

<?php
class MyHeap extends \SplMinHeap
{
    public function compare($o1, $o2)
    {
        return count($o2->elements) <=> count($o1->elements) ?: $o2->id <=> $o1->id;
    }
    public function rebuild()
    {
        $tmp = [];
        for ($i = 0, $max = $this->count(); $i < $max; $i++) {
            $tmp[] = $this->extract();
        }

        array_map(
            function ($value) {
                $this->insert($value);
            },
            $tmp
        );
    }
}

$heap->rebuild();
$o = $heap->current();
var_dump($o->id); // 3 ---(3)