2020-07-25 00:28:48

ヒープソートを自分の中で消化する

ヒープソートは順不同の数字の配列を順番に並べ替えるアルゴリズムです。簡単に思える問題でも、ゆっくりじっくり消化するのが大事だって聞いたことあるので消化します。

消化したもの

ヒープソートを学習するために何回かコードを書いていて消化していったものが以下のものです。

• ヒープ構造は配列で表現
  • 根のIndexをiとする
  • 左の節のIndexは2*i+1
  • 右の節のIndexは2*i+2
• 最初のヒープ構築では木構造の最後の節を根としてヒープ構築する
  • 配列の中央のIndexをヒープの根としてヒープ構造を構築する
• 根≦節になるように要素を交換する
  • 最終的に昇順に並び替えたい場合は根≦節
• 配列の OutOfIndex な節を参照しようとしたときの分岐必要
• 要素を交換したら再度ヒープ構造を構築する
  • 根の値が最大値として仮定する
  • ここ再帰処理ポイント
• できたヒープ構造になった配列の先頭と末尾の要素を交換する
• 配列末尾を除いた配列で再びヒープ構造を作る
• 根と節、配列のIndexの値がゴッチャゴチャになるので気をつける

消化できたか確認する

2回程カンニングしました。以下にPHPによるヒープソートのコードです。完全消化は出来ていません。消化部分も忘れちゃうんだろうなぁ。

    <?php

    /**
     * ちっさいヒープ構造を再帰的に作成
     */
    function make_min_heap_recursive($array, $root_index, $bottom_index) {
        $left_index  = 2 * $root_index + 1;
        $right_index = 2 * $root_index + 2;

        // 節が配列外の場合は何もせずに配列を返す
        if ($left_index > $bottom_index || $right_index > $bottom_index) {
            return $array;
        }

        // 根を最大値として仮定する
        $max_value_of_index = $root_index;

        if ($array[$left_index] >= $array[$max_value_of_index]) {
            // 最大値が左の節になる
            $max_value_of_index = $left_index;
        }

        if ($array[$right_index] >= $array[$max_value_of_index]) {
            // 最大値が右の節になる
            $max_value_of_index = $right_index;
        }

        // 節の値が根よりも大きい場合
        if ($max_value_of_index != $root_index) {
            // 根と節を交換
            $tmp = $array[$root_index];
            $array[$root_index] = $array[$max_value_of_index];
            $array[$max_value_of_index] = $tmp;

            // 再度ヒープ構造構築
            $array = make_min_heap_recursive($array, $max_value_of_index, $bottom_index);
        }

        return $array;
    }

    function main() {
        $array = [14,39,19,61,80,52,3];

        // OutOfIndex考慮のため配列末尾のインデックスを取得
        $bottom_index = count($array)-1;

        // 木構造の最後の節からヒープ構造構築のために配列中央から先頭に向かってヒープ構築
        for ($i=floor($bottom_index/2); $i > -1; $i--) {
            $array = make_min_heap_recursive($array, $i, $bottom_index);
        }

        // 先頭の値と末尾の値を交換する
        for ($i=$bottom_index; $i > 0; $i--) {
            $tmp = $array[0];
            $array[0] = $array[$i];
            $array[$i] = $tmp;

            // 先頭を根、末尾位置を1つ先頭側に移動して再度ヒープ構築
            $array = make_min_heap_recursive($array, 0, $i-1);
        }

        // 出力
        foreach ($array as $key => $value) {
            echo $value.' ';
        }
        echo PHP_EOL;
    }

    main();

出力結果

3 14 19 39 52 61 80