【PHP8.x】SplMinHeap::compare()メソッドの使い方

Copy
1<?php
2
3/**
4 * SplMinHeap を継承し、配列を比較するためのカスタムヒープクラスを定義します。
5 * このヒープは、内部の compare メソッドを使って配列を辞書順に並べ替えます。
6 */
7class MyArrayMinHeap extends SplMinHeap
8{
9    /**
10     * ヒープの要素を比較します。
11     * SplMinHeap は最小ヒープなので、このメソッドが負の整数を返すと
12     * $value1 が $value2 より小さい（優先される）と判断されます。
13     *
14     * キーワード「php compare arrays」に対応するため、このメソッドは配列同士を比較します。
15     *
16     * @param mixed $value1 比較する最初の値（ここでは配列を想定）
17     * @param mixed $value2 比較する2番目の値（ここでは配列を想定）
18     * @return int $value1 が $value2 より小さい場合は負の整数、等しい場合は 0、大きい場合は正の整数
19     */
20    protected function compare(mixed $value1, mixed $value2): int
21    {
22        // PHP 7で導入された宇宙船演算子 (spaceship operator) を使用します。
23        // この演算子は、左辺が右辺より小さい場合は -1、等しい場合は 0、大きい場合は 1 を返します。
24        // 配列に対して適用すると、要素を順に比較し、辞書順で結果を返します。
25        // 例えば、[1, 2] と [1, 5] を比較すると、2 < 5 なので [1, 2] が小さいと判断されます。
26        // また、[1] と [1, 2] を比較すると、[1] が短いので小さいと判断されます。
27        return $value1 <=> $value2;
28    }
29}
30
31// このスクリプトがコマンドラインから実行された場合にのみ以下のコードを実行
32if (php_sapi_name() === 'cli') {
33    echo "SplMinHeap を使用して配列を比較・ソートする例:\n\n";
34
35    // カスタムヒープのインスタンスを作成
36    $heap = new MyArrayMinHeap();
37
38    // ヒープに追加する配列のリスト
39    $arraysToAdd = [
40        [3, 1],
41        [1, 5],
42        [2, 3],
43        [1, 2],
44        [3, 0],
45        [1],    // 短い配列もテスト
46        [1, 2, 3], // 長い配列もテスト
47    ];
48
49    echo "ヒープに以下の配列を追加します:\n";
50    foreach ($arraysToAdd as $array) {
51        $heap->insert($array);
52        echo "  - [" . implode(', ', $array) . "]\n";
53    }
54
55    echo "\nヒープから最小（辞書順で最も小さい）の配列を順に取り出します:\n";
56    // ヒープが空になるまで要素を取り出す (SplMinHeap なので最小値から順に出てくる)
57    while (!$heap->isEmpty()) {
58        $minArray = $heap->extract(); // ヒープから最小の要素を取り出す
59        echo "  - [" . implode(', ', $minArray) . "]\n";
60    }
61}

PHP 8のSplMinHeapクラスは、最小値から順に要素を取り出せるデータ構造です。このSplMinHeapが要素同士の大小関係を判断するために使うのがcompareメソッドです。通常は数値などを比較しますが、このサンプルコードではMyArrayMinHeapというカスタムクラスを作成し、compareメソッドをオーバーライドして配列同士を比較できるようにしています。

compareメソッドは二つの値$value1と$value2を受け取り、その大小関係に応じて整数値を返します。$value1が$value2より小さいと判断される場合は負の整数、等しい場合は0、大きい場合は正の整数を返します。SplMinHeapは、この戻り値が負の整数であれば$value1を優先する（より小さいと判断する）ため、最小ヒープの振る舞いを決定します。

サンプルコードのcompareメソッドでは、PHP 7で導入された宇宙船演算子<=>を使用しています。この演算子は、左右の値を比較し、左辺が小さい場合は-1、等しい場合は0、大きい場合は1を返します。配列に適用すると、要素を順番に比較し、辞書順での大小関係を判断します。例えば、[1, 2]は[1, 5]よりも辞書順で小さく、また[1]は[1, 2]よりも小さいと判断されます。

このように定義されたMyArrayMinHeapに複数の配列をinsertメソッドで追加すると、内部的にはcompareメソッドを使って配列の並び順が決定されます。その後、extractメソッドで要素を取り出すと、辞書順で最も小さい配列から順に取り出される動作を確認できます。これにより、配列の辞書順ソートをヒープの機能を使って実現できます。

Copy
1<?php
2
3/**
4 * SplMinHeap を継承し、カスタムの比較ロジックを提供するヒープクラス。
5 * このクラスは、数値を降順（大きいものが優先）で並べ替えるように動作します。
6 * つまり、最小ヒープでありながら、実質的に最大ヒープのように振る舞います。
7 */
8class CustomMaxHeap extends SplMinHeap
9{
10    /**
11     * 2つの値を比較し、並び順を決定します。
12     *
13     * @param mixed $value1 比較対象の1番目の値
14     * @param mixed $value2 比較対象の2番目の値
15     * @return int $value1が$value2より小さい場合（ヒープ内で優先される場合）負の整数、
16     *             等しい場合0、大きい場合（ヒープ内で優先されない場合）正の整数を返します。
17     *             ここでは通常の数値比較とは逆のロジックを使用し、大きい値ほど「小さい」（優先される）とみなします。
18     */
19    protected function compare(mixed $value1, mixed $value2): int
20    {
21        // $value2 と $value1 を比較することで、通常の昇順比較の結果を反転させます。
22        // PHP 7以降の宇宙船演算子 (Combined Comparison Operator) を使うと簡潔に書けます。
23        // $value1 が $value2 より大きい場合に負の値を返し、ヒープ内で優先されるようにします。
24        return ($value2 <=> $value1);
25
26        /*
27         * 上記は以下のif-elseブロックと等価です:
28         *
29         * if ($value1 > $value2) {
30         *     return -1; // $value1の方が大きい場合、ヒープでは$value1を優先（小さいとみなす）
31         * } elseif ($value1 < $value2) {
32         *     return 1;  // $value2の方が大きい場合、ヒープでは$value2を優先
33         * } else {
34         *     return 0;  // 等しい場合
35         * }
36         */
37    }
38}
39
40// --- カスタムヒープのデモンストレーション ---
41
42// カスタムヒープのインスタンスを作成
43$heap = new CustomMaxHeap();
44
45echo "要素を追加: 5, 3, 8, 1, 10, 2\n";
46$heap->insert(5);
47$heap->insert(3);
48$heap->insert(8);
49$heap->insert(1);
50$heap->insert(10);
51$heap->insert(2);
52
53echo "ヒープ内の要素数: " . $heap->count() . "\n";
54
55echo "要素を抽出し、比較ロジックが正しく機能しているか確認します (大きい値から順に抽出されるはず):\n";
56while (!$heap->isEmpty()) {
57    echo "抽出: " . $heap->extract() . "\n"; // 最大値から順に抽出される
58}
59
60echo "ヒープは空になりました。\n";
61

このサンプルコードは、PHPの標準ライブラリにあるSplMinHeapクラスのcompareメソッドをオーバーライドし、ヒープが要素を並べ替える際のロジックをカスタマイズする方法を示しています。SplMinHeapは通常、最も「小さい」要素を優先的に取り出す最小ヒープとして動作しますが、compareメソッドを独自に実装することで、この比較基準を変更できます。

compareメソッドは、ヒープ内で比較される2つの値$value1と$value2を引数として受け取ります。そして、それらの相対的な順序を決定する整数値を返します。具体的には、戻り値が負の数の場合$value1が$value2より「小さい」（ヒープ内で優先される）、正の数の場合$value1が「大きい」（ヒープ内で優先されない）、0の場合両者は等しいと解釈されます。

このコードではCustomMaxHeapクラスでcompareメソッドを定義し、($value2 <=> $value1)という比較ロジックを採用しています。これは、通常の昇順比較（$value1 <=> $value2）の結果を意図的に反転させる効果があります。これにより、$value1が$value2より大きい場合に負の値が返され、ヒープは大きい値を「小さい」（つまり優先される）とみなします。その結果、本来の最小ヒープとは異なり、extractメソッドで最大値から順に要素を取り出す「最大ヒープ」として機能するようになります。

このように、compareメソッドを適切にオーバーライドすることで、プログラムの要件に応じた柔軟な要素の並べ替えロジックを持つカスタムヒープを作成できます。