ヒープソートとは、ヒープデータ構造を使用して設計されたソートアルゴリズムを指します。スタッキングは、ほぼ完全にバイナリツリーであり、スタッキングのプロパティを満たす構造です。つまり、子ノードのキー値またはインデックスは常に親ノードよりも小さく（またはそれ以上）ます。
ヒープソートの平均時間の複雑さはο（nlogn）です。
アルゴリズムのステップ：
1.ヒープH [0..N-1]を作成する
2.ヒープヘッド（最大）とヒープテールを交換します
3.ヒープのサイズを1縮小し、Shift_down（0）を呼び出します。目的は、新しい配列の上位データを対応する位置に調整することです。
4.ヒープのサイズが1になるまでステップ2を繰り返します
ヒープ：
ヒープは実際には完全にバイナリツリーであり、その非葉のノードの非葉のノードはそのプロパティを満たします：key [i] <= key [2i+1] && key [i] <= key [i]> = key [2i+1]> = key> = key [2i+2]ヒープは大きな上部の山と小さな上部の山に分かれています。満足のいくキー[i]> = key [2i+1] && key> = key [2i+2]は、大きなトップヒープと呼ばれます。満足のいくキー[i] <= key [2i+1] && key [i] <= key [2i+2]は小さな上部の山と呼ばれます。上記のプロパティから、大きな上部のヒープの上部にあるキーワードは間違いなくすべてのキーワードの中で最大であり、小さな上部のヒープの上部にあるキーワードはすべてのキーワードの中で最小であることがわかります。
ヒープソートアイデア：
大きなトップヒープの上部（小さなトップヒープ）の上部に記録されている最大のキーワード（最小キーワード）の機能により、毎回障害から最大のレコード（最小レコード）を選択することができます。基本的なアイデアは（ビッグトップヒープ）です。1）キーワードの初期シーケンスを構築して、ソートする（R1、R2….RN）を構築します。 2）ヒープ上部要素r [1]を最後の要素r [n]と交換し、新しい無秩序な領域（R1、R2、…RN-1）と新しい順序領域（RN）を取得し、R [1,2…n-1] <= r [n]を満たします。 3）交換後の新しいヒープトップR [1]はヒープの特性に違反する可能性があるため、現在の無秩序な領域（R1、R2、…RN-1）を新しいヒープに調整し、新しい障害領域の最後の要素と交換R [1]を再び交換する必要があります（R1、R2….RN-2）（RN-2）。順序付けられた領域の要素の数がN-1になり、並べ替えプロセス全体が完了するまで、このプロセスを繰り返します。操作プロセスは次のとおりです。1）ヒープの初期化：r [1..n]をヒープとして構築します。 2）現在の順序付けられていない領域のヒープ上部要素r [1]を、間隔の最後のレコードと交換し、新しい順序付けられていない領域を新しいヒープに調整します。したがって、ヒープの並べ替えの場合、最も重要な2つの操作は、初期ヒープを構築してヒープを調整することです。実際、最初のヒープを構築することは実際にはヒープを調整するプロセスですが、最初のヒープを構築することは、すべての非葉のノードを調整することです。
イラストの例
形状配列a [] = {16,7,3,20,17,8}を与えられた場合、ヒープソート。まず、配列要素に基づいて完全なバイナリツリーを構築し、取得します
次に、初期ヒープを構築し、最後の非葉のノードから調整を開始する必要があります。調整プロセスは次のとおりです。
20と16の交換後、16は16がヒープの特性を満たさないため、再調整する必要があります。
これにより、最初のヒープが得られます。
最初に調整されると、大きなトップパイルになります。
つまり、各調整は、親ノード、左の子ノード、および右の子ノードから最大のものを選択して親ノードと交換することです（交換後、子供ノードを交換してヒープの性質を満たさないようにするため、交換された子ノードを交換した後に再び調整する必要があります）。最初のヒープを使用すると、ソートできます。
この時点で、3は山の上部にあり、プロパティは山でいっぱいです。調整して調整を続ける必要があります。
このように、間隔全体はすでに秩序です。上記のプロセスから、ヒープの並べ替えは実際には一種の選択並べ替え、ツリーの選択並べ替えであることがわかります。ただし、順序を直接選択するには、r [1 ... n]から最大レコードを選択するには、n-1回を比較し、r [1 ... n-2]から最大レコードを選択する必要があります。実際、これらのN-2比較の多くは以前のN-1比較で行われており、ツリーの選択ソーティングはツリーの特性を使用して以前の比較結果の一部を保存するため、比較の数を減らすことができます。 nキーワードシーケンスの場合、最悪の場合、各ノードはlog2（n）時間を比較する必要があるため、最悪の場合の時間の複雑さはnlognです。ヒープソートは不安定であり、レコードが少ないソートには適していません。多くのことが上記で説明されています。要するに、ヒープソートの基本的な慣行は次のとおりです。まず、元のデータを使用して、元の順序付けられていない領域として大きな（小さな）ヒープを構築し、その後、ヒープ上部の要素を順序付けられた領域に取り出して配置するたびに。ヒープの上部要素が取り出されるため、ヒープのヒープの最後の要素をヒープの上部に入れて、ヒープの特性が破壊されます。ヒープを再調整してn回続ける必要があります。その後、順序付けられていない領域のn要素が順序付けられた領域に配置され、ソートプロセスが完了します。
（構築スタックは下から上にあります）
実用アプリケーション：
実際には、特定の条件下で最大値または最小値を取得するために、ヒープソートを実行します。たとえば、100の数値から10の最大値を見つける必要があります。したがって、サイズ10のヒープを定義し、最初の10個のデータを100個のデータを小さなトップヒープ（ヒープの上部）に構築し、100データの11番目のデータのヒープの上部と比較します。ヒープの上部が現在のデータよりも小さい場合、ヒープの上部がポップアップし、現在のデータをヒープの上部に押してから、ヒープの上部から特定の位置にデータを移動します。
コード：
public class test0 {static int [] arr; // heap array、有効な配列public test0（int m）{arr = new int [m];} static int size = 0; // heap public void addtosmall（int v）{// int [] a = a = adtosmallの有効なデータをマークするために使用される{16,4,5,9,1,10,11,12,13,14,15,2,3,6,7,8,111,222,333,55,66,67,54}; //ヒープサイズは10 // arr = newですint [10]; if（size <arr.length）{arr [size] = v; add_sort（size）; // add_sort1（size）; size ++;} else {arr [0] = v; add_sort1（0）;}} public void printsmall（）{in int i = 0; i <size; i ++）{system.out.println（arr [i]）;}} public void del（）{size - ; arr [0] = arr [9]; add_sort1（0）;} public void small（int index）{if（m <arr.length）{add_sort（index）; m ++;} else {add_sort1（index）; m ++;}} public void add_sort（int index）{//小さなトップヒープ、ビルドヒープ/ * *親ノード座標：index * reft * index * righ node * is a ard * is a a左子*配列の最後のものが偶数の場合、子ノードが親ノードよりも大きい場合、バリューエクスチェンジが実行されます。右の子供が左の子よりも大きい場合、値交換が実行されます**/int par; if（index！= 0）{if（index％2 == 0）{par =（index-1）/2; if（arr [index] <arr [par]）{swap（arr、index、par）; add_sort（par）;} if（arr [par*2]; dex] <arr [par]）{swap（arr、index、par）;} add_sort（par）;}} else {par = index/2; if（arr [index] <arr [par]）{swap（arr、index、par）; add_sort（par）;} if（arr [index] <arr [par*2+1] par*2+1）; if（arr [index] <arr [par]）{swap（arr、index、par）;} add_sort（par）;}}}} add_sort1（int index）{//小さなトップヒープ/*調整トップダウン*子ノードが大きい=インデックス=インデックス、Int inted*2; int inted*2; max = 0; if（left <10 && arr [左] <arr [index]）{max = left;} else {max = index;} if（右<10 && arr [右] <arr [max]）{max = right;} if（max！= index）{swap（arr、max）; add_sort1（max）;}; Import java.util.scanner; public class main_test0 {public static void main（string args []）{scanner scan = new scanner（system.in）; system.out.println（ "（small top heap）を入力してください。 {16,4,5,9,1,10,11,12,13,14,15,2,3,6,7,8};上記のJavaヒープソートの例（大きなトップヒープ、小さなトップヒープ）は、私があなたと共有するすべてのコンテンツです。参照を提供できることを願っています。wulin.comをもっとサポートできることを願っています。