PHPのSplMinHeapとSplMaxHeapを使いこなす：優先度付きキューで効率的なデータ処理を実現する

SplMinHeapとSplMaxHeapとは？

PHPの標準ライブラリ（SPL）には、SplStackやSplQueue以外にもヒープ（Heap）を扱うデータ構造が用意されています。それが SplMinHeap と SplMaxHeap です。

• SplMinHeap：常に最小値が先頭に来るヒープ
• SplMaxHeap：常に最大値が先頭に来るヒープ

ヒープとは、「親ノードが子ノードより常に大きい（または小さい）」 という性質を持つ木構造です。この性質のおかげで、最大値や最小値の取り出しが非常に高速（O(log n)）に行えます。

普通の配列で最小値を取り出すには全件を走査する必要がありますが、ヒープを使えばそのコストを大幅に削減できます。

基本的な使い方

SplMinHeap の基本操作

<?php

$heap = new SplMinHeap();

// 要素を追加する
$heap->insert(15);
$heap->insert(3);
$heap->insert(8);
$heap->insert(1);
$heap->insert(20);

// 要素数を確認する
echo $heap->count(); // 5

// 先頭（最小値）を確認する（取り出さない）
echo $heap->top(); // 1

// 先頭から順に取り出す
while (!$heap->isEmpty()) {
    echo $heap->extract() . PHP_EOL;
}
// 出力: 1, 3, 8, 15, 20（昇順）

挿入順序に関係なく、extract() を呼ぶたびに最小値から順番に取り出せるのがポイントです。

SplMaxHeap の基本操作

<?php

$heap = new SplMaxHeap();

$heap->insert(15);
$heap->insert(3);
$heap->insert(8);
$heap->insert(1);
$heap->insert(20);

while (!$heap->isEmpty()) {
    echo $heap->extract() . PHP_EOL;
}
// 出力: 20, 15, 8, 3, 1（降順）

SplMaxHeapでは最大値が先頭に来るため、今度は降順で取り出せます。

主なメソッド一覧

実践例：優先度付きタスクキュー

ヒープの典型的なユースケースが優先度付きキューです。タスクに優先度を付けて、高い優先度のものから順に処理したい場面で活用できます。

<?php

class Task
{
    public function __construct(
        public readonly string $name,
        public readonly int $priority,
    ) {}
}

// 優先度の高いタスクを先に処理するキュー
class TaskQueue extends SplMaxHeap
{
    protected function compare(mixed $a, mixed $b): int
    {
        // SplMaxHeapのcompare()をオーバーライドして比較ロジックを定義
        return $a->priority <=> $b->priority;
    }
}

$queue = new TaskQueue();

$queue->insert(new Task('メール送信',    priority: 1));
$queue->insert(new Task('決済処理',     priority: 10));
$queue->insert(new Task('ログ出力',     priority: 2));
$queue->insert(new Task('在庫チェック', priority: 8));
$queue->insert(new Task('通知送信',     priority: 5));

echo "--- タスク処理順 ---" . PHP_EOL;
while (!$queue->isEmpty()) {
    $task = $queue->extract();
    echo "優先度 {$task->priority}: {$task->name}" . PHP_EOL;
}

出力結果:

--- タスク処理順 ---
優先度 10: 決済処理
優先度 8: 在庫チェック
優先度 5: 通知送信
優先度 2: ログ出力
優先度 1: メール送信

compare() メソッドをオーバーライドすることで、カスタムオブジェクトの比較ロジックを自由に定義できます。これにより、数値だけでなくあらゆるオブジェクトをヒープで管理できます。

SplPriorityQueueとの違い

PHPにはさらに SplPriorityQueue というクラスもあります。こちらはデータと優先度を分離して扱えます。

<?php

$pq = new SplPriorityQueue();

// insert(データ, 優先度) の形で追加
$pq->insert('メール送信',    1);
$pq->insert('決済処理',     10);
$pq->insert('ログ出力',      2);

while (!$pq->isEmpty()) {
    echo $pq->extract() . PHP_EOL;
}
// 出力: 決済処理, ログ出力, メール送信

配列ソートとのパフォーマンス比較

「sort()でいいのでは？」と思うかもしれません。しかし用途が異なります。

• sort()：全件ソート。一度に全要素を並べ替えたいときに最適
• SplMinHeap/SplMaxHeap：要素を随時追加しながら、常に最小・最大を取り出したいときに最適

要素を動的に追加しながら最小値・最大値を繰り返し取り出す処理では、ヒープのほうが効率的に動作します。

まとめ

• SplMinHeap は常に最小値、SplMaxHeap は常に最大値を先頭に持つデータ構造
• insert() / extract() / top() の3つを覚えれば基本操作はOK
• compare() をオーバーライドすることでカスタムオブジェクトにも対応できる
• 優先度付きキューや「常に上位N件を保持したい」場面で特に力を発揮する

PHPでデータ構造を意識したコードを書きたいときは、ぜひ SplMinHeap と SplMaxHeap を活用してみてください。