Java プログラミングスキル - データ構造とアルゴリズム「ヒープソート」

[[389058]]

ヒープソートの基本

ヒープソートは、ヒープデータ構造を使用して設計されたソートアルゴリズムです。ヒープソートは選択ソートです。最良、最悪、平均の時間計算量はすべて O(nlogn) であり、不安定なソートです。
ヒープは、次の特性を持つ完全な二分木です。各ノードの値は、その左と右の子ノードの値以上であり、最大ヒープと呼ばれます。注: 最大子ノード値のサイズ関係は要件ではありません。
各ノードの値は、左と右の子ノードの値以下であり、これをミニヒープと呼びます。
最大ヒープ特性: arr[i ] >= arr[2i+1] && arr[i] >= arr[2i+2]、iはノード番号に対応し、iは0から始まります。
ミニヒープの特性: arr[i ] <= arr[2i+1] && arr[i] <= arr[2i+2]、iはノード番号に対応し、iは0から始まります。
一般的に、昇順の場合は大きなトップヒープが使用され、降順の場合は小さなトップヒープが使用されます。

ヒープソートの基本的な考え方

ソートするシーケンスを大きなトップヒープに構築する
この時点で、シーケンス全体の最大値はヒープの最上部にあるルートノードになります。
配列の最後の要素と交換すると、最後が最大値になります。
次に、残りの n-1 個の要素をヒープ内に再構築し、n 個の要素の次に小さい値を取得します。このプロセスを繰り返して繰り返すことで、順序付けられたシーケンスを取得できます。

最大ヒープ構築の過程で、要素数が徐々に減少し、最終的に順序付けられたシーケンスが得られることがわかります。

配列内の非リーフノードの数 = arr.length / 2 - 1

コード例

パッケージ com.xie.tree; 
 
パブリッククラスHeapSort {
公共 静的void main(String[] args) {
 int [] arr = 新しいint [8000000];
 ( int i = 0; i < 8000000; i++) {
            arr[i] = ( int ) (Math.random() * 800000000);
        }
        長い開始 = System.currentTimeMillis();
        ヒープソート(arr);
        長い終了= System.currentTimeMillis();
        System.out.println ( "所要時間:" +( end -start)+ "ms" );
        /**
         * 800万件のデータ
         * ヒープソート!!
         * 消費時間: 2482ms
         */
    } 
 
公共 静的voidヒープソート( int []arr){
整数 温度= 0;
        System.out.println ( "ヒープソート!!" ) ; 
 
        //1. 順序付けられていないシーケンスからヒープを作成し、昇順と降順の要件に従って、大きいトップ ヒープまたは小さいトップ ヒープを選択します。
 ( int i = arr.length / 2 - 1; i >= 0; i --) {  
            ヒープを調整します(arr、i、arr.length);
        }
        //2. ヒープの先頭要素を配列の末尾要素と交換し、最大の要素を配列の末尾に「シンク」します。
        //3. ヒープ定義を満たすように構造を再調整し、ヒープの最上位要素と現在の終了要素を交換し続け、シーケンス全体が整うまで調整 + 交換手順を繰り返し実行します。
 ( int j = arr.length - 1; j > 0; j --) {  
            //交換
temp = arr[j];
            arr[j] = arr[0];
            arr[0] =一時;
            ヒープを調整します(arr, 0, j);
        }
    } 
 
    /**
     * 配列（バイナリツリー）を大きなトップヒープに調整する
     * 機能: iに対応する非リーフノードのツリーを最大ヒープに調整する
     *
     * @param arr 調整する配列
     * @param i は配列内の非リーフノードのインデックスを表します
     * @param lengthは調整される要素の数を示し、長さは徐々に減少します
     */
公共 静的void調整ヒープ( int [] arr、 int i、 int長さ) {
        //まず現在の要素の値を取り出して一時変数に保存します
整数  temp = arr[i];
        //k = 2 * i + 1 はノード i の左の子ノードです
( int k = 2 * i + 1; k < 長さ; k = k * 2 + 1) {
            //左の子ノードの値が右の子ノードの値より小さい場合
            (k + 1 < 長さ && arr[k] < arr[k + 1]) の場合 {
                k++; //kは右の子ノードを指す
            } 
 
            //子ノードの値が親ノードの値より大きい場合
            もしarr[k] > tempであれば
                // 大きい方の値を現在のノードに代入する
                arr[i] = arr[k];
                //!!! iはkを指し、ループして比較を続けます
                私 = k;
            }それ以外{
                壊す;
            }
        } 
 
        // forループが終了すると、i を親ノードとするツリーの最大値を一番上に配置します。 
 
        //調整された位置に温度値を配置します
        arr[i] =一時;
    }
 }