PHP を使用してヒープ ソート アルゴリズムを作成する方法

PHP を使用してヒープ ソート アルゴリズムを作成する方法

ヒープ ソートは効率的なソート アルゴリズムです。その中心的な考え方は、ソート対象のシーケンスをバイナリ ヒープに構築し、その構造を継続的に調整することです。ソートを実現するためのヒープ。この記事では、PHP を使用してヒープ ソート アルゴリズムを作成する方法を紹介し、参考となるコード例を示します。

1. ヒープの定義
   ヒープ ソート アルゴリズムの作成を開始する前に、まずヒープの定義とプロパティを明確にする必要があります。ヒープは、次のプロパティを持つ完全なバイナリ ツリーです。任意のノード i について、次の 2 つの条件が満たされます。
2. 親ノードの値は、常に子ノードの値以上です (最大ヒープ);
3. 親ノードの値は常に子ノードの値 (最小ヒープ) 以下です。
4. ヒープ操作の調整
   ヒープを構築するには、ヒープ調整操作を実行する方法を理解する必要があります。ヒープの調整は 2 つのステップに分かれています。
5. 最後の非リーフ ノードから開始して、そのノードとその子ノードを順番に比較し、大きい (または小さい) 値をそのノードの位置に交換します。親ノード;
6. ヒープ全体の構造がヒープのプロパティを満たすまで、上記の手順を繰り返します。

以下は、PHP で実装されたヒープ調整関数の例です。

function heapify(&$arr, $n, $i) {
    $largest = $i; // 将当前节点标记为最大值节点
    $l = 2 * $i + 1; // 左子节点
    $r = 2 * $i + 2; // 右子节点

    // 如果左子节点大于根节点
    if ($l < $n && $arr[$l] > $arr[$largest]) {
        $largest = $l;
    }

    // 如果右子节点大于根节点
    if ($r < $n && $arr[$r] > $arr[$largest]) {
        $largest = $r;
    }

    // 如果最大值不等于当前节点，则交换它们的位置
    if ($largest != $i) {
        $temp = $arr[$i];
        $arr[$i] = $arr[$largest];
        $arr[$largest] = $temp;

        // 递归调整交换之后的子树
        heapify($arr, $n, $largest);
    }
}

3. ヒープ ソート アルゴリズム
   ヒープの定義とヒープ調整を行った後オペレーション、今度はヒープ ソート アルゴリズムを作成します。ヒープ ソートの主な手順は次のとおりです:
4. 最大ヒープの構築: 最後の非リーフ ノードから開始して、ヒープ調整関数を順番に呼び出して最大ヒープを構築します。 : ヒープの先頭要素 (最大値) を追加し、最後の要素と位置を交換してから、ヒープのサイズを -1 減らしてから、ヒープ調整関数を呼び出して残りの要素の順序を調整します。
ヒープのサイズが 1 になるまで上記の手順を繰り返します。1 になった時点で、すべての要素が昇順に並べ替えられます。
6. 次に、PHP で実装されたヒープ ソート関数の例を示します。

function heapSort(&$arr) {
    $n = count($arr);

    // 构建最大堆
    for ($i = ($n / 2) - 1; $i >= 0; $i--) {
        heapify($arr, $n, $i);
    }

    // 排序
    for ($i = $n - 1; $i > 0; $i--) {
        // 交换堆顶和最后一个元素
        $temp = $arr[0];
        $arr[0] = $arr[$i];
        $arr[$i] = $temp;

        // 调整剩余元素的顺序
        heapify($arr, $i, 0);
    }
}

ヒープ ソート アルゴリズムの使用

ヒープ ソート アルゴリズムの使用は非常に簡単です。ソートする必要があるのは、上記のヒープソート関数にパラメータとして配列を渡すだけです。以下は、ヒープ ソート アルゴリズムを使用して配列をソートする例です:

4. $arr = [3, 7, 2, 11, 1, 9, 6, 4, 8];
   
   echo "排序前：" . implode(", ", $arr) . "
   ";
   
   heapSort($arr);
   
   echo "排序后：" . implode(", ", $arr) . "
   ";

   
   上記のコードを実行すると、次の出力が得られます:

排序前：3, 7, 2, 11, 1, 9, 6, 4, 8
排序后：1, 2, 3, 4, 6, 7, 8, 9, 11

このようにして、書き込みに成功し、ヒープソートアルゴリズムが適用されます。

概要:

ヒープ ソートは、最大 (または最小) ヒープを構築することでソートを実装する効率的なソート アルゴリズムです。ヒープの構造を調整することで、ヒープソートを簡単に実装できます。 PHP を使用したヒープ ソート アルゴリズムの作成は比較的簡単で、ヒープ調整関数とヒープ ソート関数を記述し、ソート対象の配列をパラメータとして渡すだけでソートを実行できます。この記事の内容が、ヒープ ソート アルゴリズムを理解し、使用する際の助けになれば幸いです。

以上がPHP を使用してヒープ ソート アルゴリズムを作成する方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。