PHP を使用してヒープソートアルゴリズムを作成する方法-PHPチュートリアル-php.cn

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

PHPz

リリース： 2023-07-08 19:20:01

オリジナル

1048 人が閲覧しました

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

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

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

以下は、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);
    }
}

ログイン後にコピー

ヒープソートアルゴリズム
ヒープの定義とヒープ調整を行った後オペレーション、今度はヒープソートアルゴリズムを作成します。ヒープソートの主な手順は次のとおりです:
最大ヒープの構築: 最後の非リーフノードから開始して、ヒープ調整関数を順番に呼び出して最大ヒープを構築します。 : ヒープの先頭要素 (最大値) を追加し、最後の要素と位置を交換してから、ヒープのサイズを -1 減らしてから、ヒープ調整関数を呼び出して残りの要素の順序を調整します。
次に、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);
    }
}

ログイン後にコピー

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

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

$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 サイトの他の関連記事を参照してください。