PHP のヒープ ソート アルゴリズムの原理と時間計算量分析を学びます。

PHP のヒープ ソート アルゴリズムの原理と時間計算量分析を学習する

ヒープ ソートはヒープ データ構造に基づいたソート アルゴリズムであり、その時間計算量は次のとおりです。ああ(nlogn)。この記事では、PHP 言語のヒープ ソート アルゴリズムの原理を紹介し、コード例を示します。

1. ヒープの定義とプロパティ

ヒープのソートを学ぶ前に、まずヒープの定義とプロパティを理解する必要があります。ヒープは、各ノードの値がその子ノードの値以上である完全なバイナリ ツリーであり、このようなヒープをビッグマックス ヒープと呼びます。逆に、各ノードの値がその子ノードの値以下の場合、それをスモールトップヒープと呼びます。

ヒープの特性上、ヒープの先頭要素が最大値または最小値となるため、ヒープのソートでは通常、ソート対象の配列を完全な二分木とみなしてその特性を利用します。ソート用のヒープ。

2. ヒープ ソート アルゴリズムの原理

ヒープ ソート アルゴリズムは、主にヒープの構築とヒープの調整の 2 つのステップに分かれています。

1. ヒープの構築: 配列が大きな上部ヒープにソートされるように調整します。

手順は次のとおりです。

• 最後の非リーフ ノード (つまり、n/2-1) から開始して 1 つずつ前方にトラバースし、関数を呼び出します。ヒープの調整 (adjustHeap)。
• ヒープを調整する機能は、トップダウンのアプローチを採用して現在のノードとそのサブツリーを調整し、現在のノードがその子ノードよりも大きくなるようにします。
• アレイ全体が大きな上部ヒープに調整されるまで、上記の 2 つの手順を繰り返します。

2. AdjustHeap: 現在のノードとそのサブツリーを大きな上部ヒープに調整します。

手順は次のとおりです。

• 現在のノードの位置に基づいて、その左右の子ノードの位置を計算します。
• 現在のノードとその左右の子ノードの値を比較して、最大のノードの位置を見つけます。
• 最大ノードの位置が現在のノードの位置ではない場合、最大ノードと現在のノードの値を交換し、再帰的に自身を呼び出して、交換されたサブツリーを調整します。

3. ソート (sortHeap): ヒープの最上位要素 (つまり、配列の最初の要素) を最後のリーフ ノードと交換し、残りの n 要素に対してヒープ調整を実行します。 -1 要素。

手順は次のとおりです。

• ヒープの最上位要素を最後のリーフ ノードと交換します。
• ヒープのスコープを縮小します。つまり、ソートされた最後のリーフ ノードを無視します。
• 縮小された範囲ヒープを調整して、大きな上部ヒープの性質を維持します。
• ヒープの範囲が 1 に減るまで、上記の 3 つの手順を繰り返します。

3. PHP コードの例

次は、PHP 言語でヒープ ソート アルゴリズムを実装するためのコード例です:

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

    // 构建大顶堆
    for ($i = floor($length/2 - 1); $i >= 0; $i--) {
        adjustHeap($arr, $i, $length);
    }

    // 调整堆并排序
    for ($i = $length - 1; $i >= 0; $i--) {
        // 交换堆顶元素和最后一个叶子节点
        $temp = $arr[0];
        $arr[0] = $arr[$i];
        $arr[$i] = $temp;

        // 调整堆使其保持大顶堆性质
        adjustHeap($arr, 0, $i);
    }
}

function adjustHeap(&$arr, $i, $length) {
    $largest = $i; // 最大值的位置
    $left = $i * 2 + 1; // 左子节点的位置
    $right = $i * 2 + 2; // 右子节点的位置

    // 比较当前节点与左右子节点的值，找到最大值的位置
    if ($left < $length && $arr[$left] > $arr[$largest]) {
        $largest = $left;
    }
    if ($right < $length && $arr[$right] > $arr[$largest]) {
        $largest = $right;
    }

    // 如果最大值的位置不是当前节点的位置，则交换两个位置的值，并递归调整堆
    if ($largest != $i) {
        $temp = $arr[$i];
        $arr[$i] = $arr[$largest];
        $arr[$largest] = $temp;
        adjustHeap($arr, $largest, $length);
    }
}

// 测试
$arr = [8, 3, 6, 2, 9, 1];
heapSort($arr);
print_r($arr); // 输出 [1, 2, 3, 6, 8, 9]

4. 時間計算量の分析

ヒープソートの時間計算量は O(nlogn) です。このうち、ヒープ構築の時間計算量は O(n)、ヒープ調整の時間計算量は O(logn) です。 n 個の要素をソートする必要があるため、合計の時間計算量は O(nlogn) になります。

概要

この記事では、PHP 言語のヒープ ソート アルゴリズムの原理を詳細に紹介し、対応するコード例を示します。ヒープ ソートは、大規模な配列をソートするのに適した効率的なソート アルゴリズムです。ヒープ ソート アルゴリズムを学習することで、データ構造とアルゴリズムの理解と応用能力をさらに向上させることができます。

以上がPHP のヒープ ソート アルゴリズムの原理と時間計算量分析を学びます。の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。