概要
ヒープソートはツリー選択のソートであり、直接選択のソートを効果的に改善します。
ヒープは次のように定義されています。N要素のシーケンス（k1、k2、...、kn）、満たした場合にのみ：
当時は山と呼ばれています。ヒープの定義からわかるように、ヒープの上部要素（つまり、最初の要素）は、最小のアイテム（小さなトップヒープ）または最大のアイテム（大きな上部の山）でなければなりません。
ヒープが1次元アレイに保存されている場合、ヒープは完全にバイナリツリーに対応し、すべての非葉のノード（子供を持つノード）の値は子供の値（またはそれ以上）以上ではなく、ルートノードの値（ヒープの上部要素）が最小（または最大）です。
（a）大きなトップヒープシーケンス：（96、83、27、38、11、09）
（b）小さなトップヒープシーケンス：（12、36、24、85、47、30、53、91）
最初に、ソートされるn番号のシーケンスは、連続して保存されたバイナリツリー（1次元配列ストレージバイナリツリー）と見なされ、ストレージのオーダーを調整してヒープにし、ヒープの最上部要素を出力して、n要素の最小（または最大の）要素を取得します。次に、残りのn-1要素を再調整してヒープになり、ヒープの上部要素を出力し、n要素の中で2番目の小さな（または2番目の大きな）要素を取得します。 nノードを使用して最終的に順序付けられたシーケンスを取得するまで。このプロセスヒープソートを呼び出します。
ステップと例
ヒープソートを実装する際に解決すべき2つの問題があります。
（1）杭に分類するn番号を構築する方法。
（2）ヒープの上部要素を出力した後、残りのN-1要素を調整して新しいヒープにする方法。
ヒープメソッドを構築する（小さなトップヒープ）：
初期シーケンスのヒープを構築するプロセスは、繰り返しスクリーニングのプロセスです。
nノードの完全なバイナリツリー、最後のノードはn/2番目のノードのサブツリーです。
フィルターは、n/2番目のノードをルート（n/2はサブツリーの最後のノード）としてサブツリーから始まり、サブツリーがヒープになります。
次に、各ノードでサブツリーを順番にルートとしてろ過し、ルートノードになるまでヒープにします。
図に示すように、ヒープを構築する初期プロセスの無秩序な配列：（49、38、65、97、76、13、27、49）
（a）順序付けられていないシーケンス、初期バイナリツリー、97（8/2 = 4ノード）は、最後のノードの親ノード（49）です。
（b）97> = 49、位置を交換し、N/2の前のノード65をフィルタリングします。
（c）13 <= 27および65> = 13、65と13の位置を交換してから、38（両方ともそれよりも大きい、操作は不要）、フィルター49を交換します。
（d）13 <= 38および49> = 13、49および13、49> = 27の位置を交換し、49と27の位置を交換します。
（e）最終的にヒープを取得します。13は最小数です。
ヒープを調整する方法（小さな上部の山）：
M要素のヒープが提供されています。ヒープの上部要素を出力した後、M-1要素が残っています。ヒープの下部要素はヒープの上部に供給され、ルートノードがヒープのプロパティを満たしていないため、ヒープが破壊されます。
ルートノードを左および右のサブツリーの小さな要素と交換します。
左サブツリーと交換する場合：左サブツリーヒープが破損している場合は、方法（2）を繰り返します。
右のサブツリーと交換する場合は、右のサブツリーヒープが破壊されている場合は、方法（2）を繰り返します。
葉のノードとヒープが構築されるまで、ヒーププロパティを満たさないサブツリーで上記の交換操作を続けます。
ヒープを調整するには、破損したノードを考慮するだけで、他のノードを調整する必要はありません。
コード実装（Java）
コードを実行し、コメントを上記の例の手順で比較するために比較します。
パッケージcom.coder4j.main; public class heapsort { / ** *小さなトップヒープに調整します（結果は並べ替え後に大きくなります） tmp = array [s]; int child = 2 * s + 1; //左の子ノードシステムの位置.out.println（ "調整するノードは次のとおりです。配列[" + s + "] =" + tmp）; while（child <length）{// child + 1は現在ノードを調整している右子です} system.out.println（ "child array [" + child + "] =" + array [child] + "compare"）; //小さい子供がこのノードよりも小さい場合、if（array [s]> array [child]）{system.out.println（ "子はそれよりも小さい、スワップ位置"）; array [s] = array [child]; //小さい子供を上方に移動し、現在のノードを置き換えて調整します。子= 2 * s + 1; //調整されるノードを調整する必要があるかどうかを判断し続けます（child> = length）{system.out.println（ "子供はいません、調整は終了しました"）; } else {system.out.println（ "新しい子と比較し続ける"）; } // 続く; } else {system.out.println（ "子供は自分より年上で、調整は終了しました"）;ブレーク; //調整する現在のノードは左および右の子供よりも小さい、そしてそれは直接調整する必要はありません、直接出口}}/ ** *大きなトップヒープに調整 * heapadjustb（int [] array、int s、int length）{int tmp = array [s]; int child = 2 * s + 1; //左の子ノードシステムの位置.out.println（ "調整するノードは次のとおりです。配列[" + s + "] =" + tmp）; while（child <length）{// child + 1は現在ノードを調整している右子です} system.out.println（ "child array [" + child + "] =" + array [child] + "compare"）; //年長の子供がこのノードよりも大きい場合if（array [s] <array [child]）{system.out.println（ "子はそれよりも大きい、スワップ位置"）; array [s] = array [child]; //年長の子供を上方に移動し、現在のノードを置き換えます。子= 2 * s + 1; //調整されるノードを調整する必要があるかどうかを判断し続けます（child> = length）{system.out.println（ "子供はいません、調整は終了しました"）; } else {system.out.println（ "新しい子と比較し続ける"）; } // 続く; } else {system.out.println（ "子供は自分よりも小さい、調整は終わった"）;ブレーク; //調整される現在のノードは左および右の子供よりも大きく、調整なしで直接終了します}}/ ** *ヒープソーティングアルゴリズム * * @param array * @param array * @param inverse true ructure order */ public static void heapsort（int、boolean inverse） / 2、各ノードを上方に調整してヒープシステムに準拠するように調整します。out.println（ "初期ヒープスタート"） for（int i =（array.length-1） / 2; i> = 0; i-）{if（inverse）{heapadjusts（array、i、array.length）; } else {heapadjustb（array、i、array.length）; }} system.out.println（ "初期ヒープエンド"）; for（int i = array.length-1; i> 0; i--）{//ヒープ上部要素h [0]とヒープint tmp = array [i]の最後の要素を交換します。配列[i] = array [0];配列[0] = TMP; //ヒープ上部要素とヒープの最後の要素を各スワップした後、（逆）{heapadjusts（array、0、i）;の場合、ヒープを調整する必要があります。 } else {heapadjustb（array、0、i）; }}} public static void main（string [] args）{int [] array = {49、38、65、97、76、13、27、49}; heapsort（array、false）; for（int i：array）{system.out.print（i + ""）; }}}実行結果：
最初のヒープの開始時に調整するノードは次のとおりです。配列[3] = 97子供は子供の配列とともに小さくなります[7] = 49子供は子供の場合は小さくなり、調整の終わりに調整するノードは次のとおりです。配列[1] = 38子供の配列で子供は大きい[3] = 49子供の配列で子供は大きい[0] = 49子供は子供の配列で小さくなります[2] = 13子供は子供の配列で小さくなります[6] = 27子供は交換位置よりも小さく、交換位置には子供がいません。調整後に調整するノードは次のとおりです。配列[0] = 97子供は子供よりも小さい。子供は子供よりも小さいです。交換位置は引き続き新しい子供と比較されます。子供はアレイ[6] = 49子供は交換位置よりも小さいので、交換位置に子供はいません。調整後に調整するノードは次のとおりです。配列[0] = 97子供は子供よりも小さい。子供は子供よりも小さいです。子供は子供よりも小さいです。子供はアレイです[1] = 38子供は子供よりも小さいです。子供は配列です[3] = 49子供は子供よりも小さいです。子供は交換位置よりも小さい。調整後に調整するノードは次のとおりです。配列[0] = 65子供は配列[1] = 49子供は子供よりも小さい、交換位置は新しい子供と比較され続けます。子供は子供よりも大きくなります。調整後に調整するノードは次のとおりです。配列[0] = 76子供は子供よりも大きい。調整後に調整するノードは次のとおりです。配列[0] = 76子供は子供よりも小さい。調整後に調整するノードは次のとおりです。配列[0] = 49子供は子供よりも小さい。調整後に調整するノードは次のとおりです。配列[0] = 97子供は子供よりも小さい。調整後に調整するノードは次のとおりです。配列[0] = 97 76 65 49 49 38 27 13
PS：ヒープの並べ替えと直接挿入並べ替えの違い
直接選択順序では、R [1..N]の最小キーワードでレコードを選択するには、n-1の比較を実行する必要があり、r [2..n]の最小キーワードでレコードを選択する必要があります。N-2比較を実行する必要があります。実際、次のN-2比較では、以前のN-1比較では多くの比較が行われた可能性がありますが、これらの比較結果は以前の順序で保持されなかったため、これらの比較操作は次の順序で繰り返されました。
ヒープソートは、樹木構造を通じて比較結果の一部を節約でき、比較の数を減らすことができます。