ヒープは、データ構造の重要な構造です。 「ヒープ」の概念と操作を理解した後、ヒープの並べ替えをすばやくマスターできます。
ヒープの概念
ヒープは特別な完全なバイナリツリーです。完全にバイナリツリーのすべてのノードの値が子供よりも小さくない場合、それは大きなルートヒープ（または大きな上部の山）と呼ばれます。すべてのノードの値が子供よりも大きくない場合、それは小さなルートヒープ（または小さな上部のヒープ）と呼ばれます。
配列（サブスクリプト番号0にルートノードを保存）では、次の方程式を取得するのは簡単です（これらの2つの方程式は非常に重要です）：
1. subscriptを持つノードはiで、親ノードの座標は（I-1）/2です。
2。添え字のノードはiで、左の子ノードの座標は2*i+1、右の子ノードは2*i+2です。
ヒープの確立とメンテナンス
ヒープは複数の操作をサポートできますが、今では2つの問題しか気にしません。
1.順序付けられていないアレイを考えると、ヒープとしてそれを構築する方法は？
2。ヒープの上部要素を削除した後、構成を新しいヒープに調整する方法は？
最初に2番目の質問を見てみましょう。すでに既製の大きなルートパイルがあるとします。次に、ルート要素を削除しますが、他の要素は移動しません。何が起こったのかを考えてください：ルート要素は空ですが、他の要素はまだヒープのプロパティを維持します。最後の要素（コード名A）をルート要素の位置に移動できます。特別なケースでない場合、ヒープの特性が破壊されます。しかし、これは単に、Aがその子要素の1つよりも小さいからです。したがって、Aとこの子要素を位置に切り替えることができます。 Aがすべての子要素よりも大きい場合、ヒープが調整されます。それ以外の場合、上記のプロセスを繰り返し、要素Aは適切になるまでツリー構造に「沈み」続け、アレイはヒープのプロパティを復元します。上記のプロセスは一般に「スクリーニング」と呼ばれ、方向は明らかに上から下にあります。
これは、要素を削除するときに真であり、新しい要素を挿入することもそうです。違いは、新しい要素を最後に配置してから、その親ノードと比較することです。つまり、ボトムアップからフィルタリングします。
それで、最初の問題を解決する方法は？
私が読んだデータ構造に関する本の多くは、ルート要素がフィルタリングされるまで、最初の非葉のノードからフィルタリングしています。この方法は「フィルタリング方法」と呼ばれ、n/2要素をループフィルタリングする必要があります。
しかし、「何もないところから何かを作成する」という考えから学ぶこともできます。最初の要素をヒープと見なしてから、常に新しい要素を追加できます。この方法は「挿入方法」と呼ばれ、（n-1）要素のループ挿入が必要です。
フィルタリング方法と挿入方法は異なるため、それらが作成するヒープは一般に同じデータに対して異なります。
ヒープの大まかな理解の後、ヒープの並べ替えは自然なものです。
アルゴリズムの概要/アイデア
上昇するシーケンスが必要ですが、どうすればよいですか？最小限のヒープを構築し、毎回ルート要素を出力できます。ただし、この方法には余分なスペースが必要です（それ以外の場合は、多くの要素の動きを引き起こし、その複雑さはO（n^2）に急上昇します）。インプレースソートが必要な場合はどうなりますか（つまり、O（n）スペースの複雑さが許可されていません）？
方法があります。最大ヒープを構築でき、最後の位置に最大値を出力し、最後の位置に2番目の最大値を出力できます...毎回最大要素出力が最初のスペースを解放するため、追加のスペースを必要とせずにそのような要素を配置できます。とても美しいアイデアですよね？
public class Heapsort {public static void main（string [] args）{int [] arr = {50、10、90、30、70、40、80、60、20}; System.out.println（ "sorting前に："）; for（int i = 0; i <arr.length; i ++）{system.out.print（arr [i]+""）; } //ヒープソートHeapsort（arr）; System.out.println（）; system.out.println（ "並べ替え後："）; for（int i = 0; i <arr.length; i ++）{system.out.print（arr [i]+""）; }} / ***ヒープソート* / private static void heapsort（int [] arr）{//シーケンスを構築して、（int i = arr.length / 2; i> = 0; i-）{heapadjust（arr、i、arr.length）; } //各最大値のルートノードをEnd要素と徐々に交換し、バイナリツリーを調整して、（int i = arr.length-1; i> 0; i-）{swap（arr、0、i）; // Heap Top Recordを、現在未解決のサブシーケンスHeapadjust（arr、0、i）の最後のレコードと交換します。 //交換後、ヒープが大きなトップヒープを満たしているかどうかを再確認する必要があります。会合しない場合は、調整する必要があります}} / ***ヒープを構築するプロセス* @param arrayをソートする必要がある* @param @param i arrayの長さ* @param nのルートノードの数* @param n* / private static void heapadjust（int i、int i、int child; int父; for（father = arr [i]; leftchild（i）<n; i = child）{child = leftchild（i）; //左サブツリーが右サブツリーよりも小さい場合、右サブツリーを親ノードと比較する必要があります。 //シリアル番号を1で増やし、右のサブツリーを指して} //親ノードが子ノードよりも小さい場合、（父<arr [子]）{arr [i] = arr [child]; } else {break; //大きなトップヒープ構造は破壊されません。調整は必要ありません}} arr [i] =父。 } //左の子ノードプライベートstatic int leftchild（int i）{return 2 * i + 1; } //スワップ要素位置private static void swap（int [] arr、int index1、int index2）{int tmp = arr [index1]; arr [index1] = arr [index2]; arr [index2] = tmp; }}