ホームページ > 記事 > バックエンド開発 > PHP ヒープソートの実装コード

PHP ヒープソートの実装コード

小云云オリジナル: 2018-03-22 09:31:401379ブラウズ

ヒープは、最下層を除いて完全なバイナリツリーとみなすことができ、これによりヒープを配列で表すことができ、各ノードは配列内の要素に対応します。
配列とヒープの関係:
バイナリヒープは一般に、最大ヒープと最小ヒープの 2 つのタイプに分類されます。
最大ヒープ: ヒープ内の各親ノードの要素値がその子ノード (存在する場合) 以上です。

最小ヒープ: ヒープ内の各親ノードの要素値が以下です。その子ノード (存在する場合) ;

ヒープソートとは

ヒープソート (最大ヒープが使用されると仮定) は、ヒープの先頭から最大値を取り出し、残りのヒープを最大値に調整し続けることです。ヒープ

ヒープ並べ替えアルゴリズム

ヒープの構築: ヒープの構築は常に調整されています。ヒーププロセスは len/2 から開始され、最初のノードまで調整されます。ここで、len はヒープ内の要素の数です。ヒープを構築するプロセスは線形プロセスであり、ヒープを調整するプロセスは常に len/2 から 0 まで呼び出されます。これは、o(h1) + o(h2) ...+ o(hlen/2) と同等です。ここで、h はノードの深さを表し、len /2 はノードの数を表します。これは合計プロセスであり、結果は線形 O(n) です。

調整ヒープ: 調整ヒープは、ヒープの構築プロセスで使用され、ヒープの並べ替えプロセスでも使用されます。アイデアは、ノード i とその子ノード left(i) および right(i) を比較し、最大 (最小)

値がノード i ではなくそのいずれかの場合に、3 つのうちの最大 (または最小) を選択することです。子ノード、ノード i およびそこにあるノードと対話し、ヒープ調整プロセスを呼び出します。これは再帰的なプロセスです。ヒープを調整するプロセスの時間計算量は、ヒープの深さに関係します。これは、深さ方向に沿って調整されるため、ログオン操作になります。

ヒープソート: ヒープソートは上記の2つのプロセスを使用して実行されます。 1 つ目は、要素に基づいてヒープを構築することです。次に、ヒープのルートノードを取り出し (通常は最後のノードと交換します)、最初の len-1 ノードのヒープ調整プロセスを続行し、すべてのノードが取り出されるまでルートノードを取り出します。ヒープソートプロセスの時間計算量は O(nlogn) です。ヒープの構築の時間計算量は O(n) (1 回の呼び出し) であり、ヒープの調整の時間計算量は logn であり、

の調整には n-1 回かかるため、ヒープのソートの時間計算量は O(nlogn) です。。

例:

<?php
// PHP 堆排序算法实现、堆排序时间复杂度分析
/**
 * 堆排序
 * @param array $arr
 */
function heap_sort(array &$arr)
{
    $count = count($arr);
    // 建堆 (下标小于或等于floor($count/2)-1的节点都是要调整的节点)
    for($i = floor($count / 2) - 1; $i >= 0; $i --)
    {
        heap_adjust($arr, $i, $count);
    }
    // 调整堆
    for($i = $count - 1; $i >= 0; $i--)
    {
        //将堆顶元素与最后一个元素交换
        swap($arr,0,$i);
        heap_adjust($arr,0,$i - 1);
    }
}
/**
 * 交换2个值
 * @param array $arr
 * @param int $a 数组下标
 * @param int $b 数组下标
 */
function swap(array &$arr, $a, $b)
{
    $temp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $temp;
}
/**
 * 交换2个值
 * @param array $arr
 * @param int $start 数组下标
 * @param int $end 数组下标
 */
function heap_adjust(array &$arr, $start, $end)
{
    $temp = $arr[$start];
    //沿关键字较大的孩子节点向下筛选，这里数组开始下标识0
    for($j = 2 * $start + 1; $j <= $end; $j = 2 * $j + 1)
    {
        if($j != $end && $arr[$j] < $arr[$j + 1])
        {
            $j ++;
        }
        if($temp < $arr[$j])
        {
	        //将根节点设置为子节点的较大值
	        $arr[$start] = $arr[$j];
	        $start = $j;
        }
    }
    $arr[$start] = $temp;
}
// 使用
$arr = array(8,4,2,9,3,7,1,6,5);
heap_sort($arr);
print_r($arr);

出力:

Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 [4] => 5 [5 ] => 6 [6] => 7 [7] => 8 [8] => 9 )

時間計算量の分析

一般に、ヒープソートの時間計算量は O(nlogn) です。ヒープソートは元のレコードのソート状態に影響されないため、最高、最低、平均の時間計算量は O(nlogn) です。これは、バブリング、単純な選択、直接挿入の O(n^2) 時間計算量よりも明らかにパフォーマンスがはるかに優れています。

ヒープソートは不安定なソート方法です(ソート前後で同じ要素の順序が変わる可能性があります)。

PHP ヒープソートの実装コード

ヒープ ソートとは

ヒープ並べ替えアルゴリズム

関連記事

ヒープソートとは