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

Copy
1<?php
2
3/**
4 * Demonstrates the usage of SplMaxHeap and its key() method during iteration.
5 *
6 * SplMaxHeap is a data structure that keeps the maximum element at the top.
7 * It implements the Iterator interface, allowing traversal of its elements.
8 * The key() method provides an internal identifier for each element during iteration.
9 */
10function demonstrateSplMaxHeapKey(): void
11{
12    // 1. Create a new SplMaxHeap instance.
13    $heap = new SplMaxHeap();
14
15    // 2. Insert some elements into the heap.
16    // The heap automatically arranges them so the largest is always accessible at the top.
17    echo "Inserting elements into SplMaxHeap:\n";
18    echo "  - Inserting: 10 (first element, insertion order 0)\n";
19    $heap->insert(10);
20    echo "  - Inserting: 5 (second element, insertion order 1)\n";
21    $heap->insert(5);
22    echo "  - Inserting: 20 (third element, insertion order 2)\n";
23    $heap->insert(20);
24    echo "  - Inserting: 15 (fourth element, insertion order 3)\n";
25    $heap->insert(15);
26
27    echo "\n";
28
29    // 3. Access the top element (the maximum value) without removing it.
30    // The top() method checks if the heap is not empty before returning the top element.
31    if (!$heap->isEmpty()) {
32        echo "Top element (maximum value): " . $heap->top() . "\n"; // Expected: 20
33    }
34
35    echo "\n";
36
37    // 4. Iterate over the heap to demonstrate current() and key() methods.
38    // The iteration order is from the highest value to the lowest value.
39    // The key() method for SplHeap returns an internal integer that represents
40    // the original zero-based insertion order of the element, not its value
41    // or its current position within the heap structure.
42    echo "Iterating over SplMaxHeap elements (highest to lowest value):\n";
43    // rewind() resets the iterator to the beginning.
44    for ($heap->rewind(); $heap->valid(); $heap->next()) {
45        // valid() checks if the current position is valid (i.e., if an element 'exists').
46        // If valid, then current() and key() can be safely called.
47
48        // Get the current element's value.
49        $currentValue = $heap->current();
50
51        // Get the current element's iterator key.
52        // This key indicates when the element was originally inserted relative to others.
53        $currentKey = $heap->key();
54
55        echo "  - Key (original insertion order): " . $currentKey . ", Value: " . $currentValue . "\n";
56    }
57
58    echo "\n";
59
60    // 5. Extract elements one by one (this removes elements from the heap).
61    // Elements are always extracted in maximum-priority order (highest value first).
62    echo "Extracting elements from SplMaxHeap (highest to lowest value):\n";
63    while (!$heap->isEmpty()) {
64        $extractedValue = $heap->extract();
65        echo "  - Extracted: " . $extractedValue . ", New top: " . ($heap->isEmpty() ? "N/A (heap empty)" : $heap->top()) . "\n";
66    }
67
68    echo "\n";
69    echo "Heap is now empty.\n";
70}
71
72// Execute the demonstration function.
73demonstrateSplMaxHeapKey();
74
75?>

SplMaxHeapは、PHPで利用できるデータ構造の一つで、追加された要素の中から常に最大の値を先頭に保つ特殊な配列のようなものです。このクラスは、ループ処理で要素を一つずつ取り出す際に、現在注目している要素に紐付けられた「キー」を取得するためのkey()メソッドを提供します。

key()メソッドは引数を一切取らず、戻り値はmixed型と定義されていますが、SplMaxHeapにおいては、その要素がヒープに最初に挿入された順番を示す、ゼロベースの整数値を返します。これは要素自体の値や、ヒープ内でのその要素の現在の物理的な位置を示すものではなく、あくまで挿入時の履歴を表すものです。

サンプルコードでは、forループを使ってSplMaxHeapの要素を、値が大きいものから小さいものへと順にたどっています。このループ内でcurrent()メソッドを使って要素の「値」を取得し、同時にkey()メソッドを使ってその要素が何番目に挿入されたかを示す「キー」を取得しています。例えば、ループの各ステップで要素が有効に存在するかどうか（key existsするかどうか）はvalid()メソッドで確認でき、その上でcurrent()やkey()を安全に呼び出すことができます。このようにkey()メソッドは、要素の挿入順を追跡したい場合に便利です。

Copy
1<?php
2
3/**
4 * SplMaxHeap の key() メソッドの使用例。
5 *
6 * SplMaxHeap は、要素を挿入すると自動的に最大値が常に先頭に来るように並べ替えるヒープ構造です。
7 * key() メソッドは、現在ヒープの先頭にある要素（最大値）に関連付けられた内部的なキーを返します。
8 * このキーは、通常、要素がヒープに追加された順序を示す整数値（0から始まるインデックス）となります。
9 */
10function useSplMaxHeapKeyMethod(): void
11{
12    // SplMaxHeap の新しいインスタンスを作成します。
13    // 最大値が常に先頭に来るように要素を管理します。
14    $heap = new SplMaxHeap();
15
16    // ヒープに複数の要素を挿入します。
17    // PHPのSplHeapでは、key()は通常、要素が挿入された順序（0, 1, 2, ...）を返します。
18    // 挿入順: apple (0), banana (1), cherry (2)
19    $heap->insert('apple');
20    $heap->insert('banana');
21    $heap->insert('cherry');
22
23    echo "--- ヒープの初期状態 ---\n";
24    // ヒープが空でない場合、現在の最大値とそれに関連付けられたキーを表示します。
25    // 'cherry' が最も大きく、これが現在の要素となります。
26    if (!$heap->isEmpty()) {
27        echo "現在の最大値 (current()): " . $heap->current() . "\n";
28        echo "現在の要素のキー (key()): " . $heap->key() . "\n"; // 'cherry' の挿入順インデックス (通常は2)
29    } else {
30        echo "ヒープは空です。\n";
31    }
32
33    echo "\n--- 要素を抽出しながらキーを確認 ---\n";
34    // ヒープが空になるまでループし、要素を一つずつ抽出（取り出し）ながら、
35    // その都度現在の最大値とキーを確認します。
36    while (!$heap->isEmpty()) {
37        // 抽出前の現在の最大値とキーを取得します。
38        $currentValueBeforeExtract = $heap->current();
39        $currentKeyBeforeExtract = $heap->key();
40
41        echo "抽出前の最大値: " . $currentValueBeforeExtract . ", キー: " . $currentKeyBeforeExtract . "\n";
42
43        // ヒープから最大値の要素を抽出し、ヒープを再構築します。
44        // 抽出された要素はヒープから削除されます。
45        $extractedValue = $heap->extract();
46        echo "  抽出された値: " . $extractedValue . "\n";
47
48        // 要素を抽出した後、ヒープがまだ空でなければ、新しい最大値とキーを表示します。
49        if (!$heap->isEmpty()) {
50            echo "  抽出後の最大値: " . $heap->current() . ", キー: " . $heap->key() . "\n";
51        } else {
52            echo "  ヒープは空になりました。\n";
53        }
54        echo "--------------------\n";
55    }
56}
57
58// 定義した関数を実行し、SplMaxHeap の key() メソッドの動作を確認します。
59useSplMaxHeapKeyMethod();

PHPのSplMaxHeapは、要素を挿入すると自動的に最大値が常に先頭に来るよう並べ替えるデータ構造です。 このSplMaxHeapクラスのkey()メソッドは、引数なしで、現在ヒープの先頭にある最大値の要素に関連付けられた内部的なキーをmixed型で返します。通常、このキーは要素がヒープに追加された順序を示す0から始まる整数値です。

サンプルコードでは、複数の要素をヒープに挿入後、current()で現在の最大値、key()でそのキーを表示しています。key()は、最大値となった要素に対応するキーを返します。

その後、ヒープから要素をextract()（取り出し）しながらkey()メソッドの挙動を追っています。extract()によって最大値の要素が取り除かれると、ヒープは再構築され、次に大きい要素が新たな最大値として先頭に移動します。その際、key()メソッドは、その新しい最大値に対応するキーを返します。これにより、key()メソッドが常にヒープの現在の最大値に対応する内部キーを提供することを確認できます。