Java ソートアルゴリズムの概要 (VI): ヒープソート

ヒープソートとは、ヒープツリー (ヒープ) のデータ構造を使用して設計されたソートアルゴリズムのことで、配列の特性を利用して、指定されたインデックスの要素をすばやく見つけることができます。ヒープソートは、補助空間が O(1)、最悪時間計算量が O(nlog2n) の不安定なソート方法です。ヒープソートの平均パフォーマンスは、最悪のパフォーマンスに近くなります。

ヒープソートでは、大きなルートヒープ（または小さなルートヒープ）の最上位レコードのキーワードが ***（または最小）キーワードであるという特徴を利用し、現在の順序付けされていない領域で ***（または最小）キーワードを持つレコードを簡単に選択できるようにします。

（１）大ルートヒープソートを使用する基本的な考え方

①まず、初期ファイルR[1..n]を大きなルートヒープに構築します。これは、初期の順序付けされていない領域です。

②次に、レコードR[1]（つまりヒープの先頭）を順序なし領域の最後のレコードR[n]と交換し、新しい順序なし領域R[1..n-1]と順序付き領域R[n]を取得し、R[1..n-1].keys≤R[n].keyを満たす。

③交換後の新しいルートR[1]はヒープ特性に違反する可能性があるため、現在の順序付けられていない領域R[1..n-1]をヒープに調整する必要があります。次に、R[1..n-1]の最後のキーを持つレコードR[1]を、間隔内の最後のレコードR[n-1]と交換します。これにより、新しい順序なし領域R[1..n-2]と順序付き領域R[n-1..n]が得られ、関係R[1..n-2].keys≤R[n-1..n].keysが満たされます。同様に、R[1..n-2]をヒープに調整する必要があります。

…

順序付けされていない領域に要素が 1 つだけになるまで。

（２）ビッグルートヒープソートアルゴリズムの基本操作：

① 初期化操作：初期ヒープとしてR[1..n]を構築する。

②各ソートラウンドの基本操作：現在の順序なし領域の最上位レコードR[1]をその領域の最後のレコードと交換し、新しい順序なし領域をヒープ（再構築ヒープとも呼ばれる）に調整します。

知らせ：

① ソート操作はn-1回のみで、より大きなn-1個のキーワードを選択することでファイルを昇順にソートすることができます。

② 小さいルートヒープを使用したソートは、ソート結果が降順になることを除いて、大きいルートヒープを使用した場合と似ています。ヒープソートは、直接選択ソートの逆です。ヒープソートでは、いつでも、順序付けされていない領域が順序付けされた領域の前にあり、順序付けされた領域は、元のベクトルの末尾から先頭に向かって、ベクトル全体まで徐々に拡張されます。

コード実装:

公共 クラステスト{
公共 静的  int [] Heap = { 10 , 32 , 1 , 9 , 5 , 7 , 12 , 0 , 4 , 3 }; // プリセットデータ配列 
公共 静的  void main(文字列args[]) {
 int i; // ループカウント変数 
 int Index = Heap.length; // データインデックス変数 
 System.out.print( "ソート前: " );
 (i = 1 ; i < インデックス - 1 ; i++)の場合
System.out.printf( "%3s" , ヒープ);
 System.out.println( "" );
 HeapSort(Index - 2 ); // ヒープソート 
 System.out.print( "ソート後: " );
 (i = 1 ; i < インデックス - 1 ; i++)の場合
System.out.printf( "%3s" , ヒープ);
 System.out.println( "" );
 }
 /**
 * ヒープを構築する
*/    
公共 静的  void CreateHeap( intルート、 intインデックス) {
 int i, j; // ループカウント変数 
 int Temp; // 一時変数 
 int Finish; // ヒープが構築されているかどうかを判定する 
 j = 2 * Root; // 子ノードのインデックス 
 Temp = Heap[Root]; // Heapのルート値を一時的に保存する 
 Finish = 0 ; // デフォルトのヒープ作成はまだ完了していません 
 while (j <= インデックス && 終了 == 0 ) {
 if (j < Index) // ***の子ノードを見つける 
 （ヒープ[j] < ヒープ[j + 1 ]）の場合
j++;
 (Temp >= Heap[j])の場合
Finish = 1 ; // ヒープの作成が完了しました 
それ以外{
 Heap[j / 2 ] = Heap[j]; // 親ノード = 現在のノード 
 2 * j = 2;
 }
 }
 Heap[j / 2 ] = Temp; // 親ノード = ルート値 
 }
公共 静的  voidヒープソート( intインデックス) {
整数i, j, 温度;
 // バイナリツリーをヒープに変換する 
 (i = (インデックス / 2 ); i >= 1 ; i--)の場合
ヒープを作成します(i, インデックス);
 // ヒープソートを開始 
 (i = インデックス - 1 ; i >= 1 ; i--) {
 Temp = Heap; // Heapのルート値を最後の値と交換する 
ヒープ = ヒープ[ 1 ];
ヒープ[ 1 ] = 一時;
 CreateHeap( 1 , i); // 残りの値のヒープを再構築します 
 System.out.print( "ソート: " );
 (j = 1 ; j <= インデックス; j++)の場合
System.out.printf( "%3s" ,ヒープ[j]);
 System.out.println( "" );
 }
 }
 }

ヒープはツリーとして表示され、ヒープ内のノードの高さは、ノードからリーフノードへの最長の単純な降順パス上のエッジの数として定義できます。ヒープの高さは、ツリーのルートの高さとして定義されます。ヒープ構造に対するいくつかの基本的な操作は、ツリーの高さに比例する時間、O(lgn) で実行されることがわかります。この記事がお役に立てれば幸いです。

【編集者のおすすめ】