1。基本的な知識
私たちが通常ヒープと呼ぶものは、完全なバイナリツリーまたはほぼ完全なバイナリツリーとも呼ばれるバイナリヒープを指します。バイナリヒープは、最大のヒープと最小のヒープに分かれています。
ヒープソートとは、ヒープデータ構造を使用して設計されたソートアルゴリズムを指します。これは、一種のソート選択です。アレイの特性を使用して、指定されたインデックスの要素をすばやく見つけることができます。アレイはインデックスに基づいて要素を直接取得でき、時間の複雑さはO（1）、つまり定数であるため、値の獲得には非常に効率的です。
最大ヒープの特性は次のとおりです。
最小ヒープの特性は次のとおりです。
2。アルゴリズムの考え
1.最大のヒープのアルゴリズムのアイデアは次のとおりです。
まず、初期r [0…n-1]は最大のヒープに組み込まれています。現時点では、順序付けられていないヒープです。ヒープトップは最大の要素であり、その後、順序付けられていない領域の最後のレコードr [n-1]が交換されます。これにより、新しい順序付けられていないエリアR [0…n-2]と順序付けられた領域r [n-1]になり、r [0…n-2]を満たします。Keys≤r[n-1] .key
最初のr [0…n-2]は、交換後の最大ヒープの特性を満たさない可能性があるため、最初のr [0…n-2]は、r [0]の最後の要素のみが調整されるまで最大ヒープに調整されます。
最大ヒープソートが完了した後、実際には上昇するシーケンスになります。ヒープが調整されるたびに、最大の要素が取得され、現在のヒープの最後の要素と交換されます。したがって、得られた最終シーケンスは昇順シーケンスです。
2。最小のヒープのアルゴリズムのアイデアは次のとおりです。
まず、初期r [0…n-1]は最小のヒープに組み込まれています。現時点では、順序付けられていないヒープです。ヒープの上部要素は最小の要素であり、その後、順序付けられていない領域の最後のr [n-1]と上部r [0]を交換し、それにより新しい順序付けられていないヒープr [0…n-2]と順序付きヒープr [n-1]を取得し、r [0…n-2]を満たす。
最初のr [0…n-2]は交換後の最小ヒープの特性を満たしていない可能性があるため、最初のr [0…n-2]は、r [0]の最後の要素のみが調整され、最小ヒープがソートされるまで最小ヒープに調整されます。最小ヒープの順序付けが完了した後、実際には下降シーケンスになります。ヒープが調整されるたびに、最小の要素が取得され、現在の順序付けられていないヒープの最後の要素と交換されるため、取得されたシーケンスは降下順になります。
ヒント：ヒープの並べ替えのプロセスは、実際には順序付けられた領域を継続的に拡大し、次に秩序ある領域のみがあるまで無秩序な領域を継続的に縮小するプロセスです。
3。分類プロセス分析
アルゴリズムは比較的抽象的であるため、ここでは、小さな例を挙げて、ヒープの並べ替えのプロセスを直接説明します。次に、この秩序化されていないシーケンスを使用して、ヒープソートに最大のヒープを使用し、結果のシーケンスは上昇シーケンス（ASC）です。
注文されていないシーケンス：89、-7,999、-89,7,0、-888,7、-7
ステップ1：構築する最大ヒープを初期化します。
ステップ2：999が順序付き領域になるように、順序付けられていない領域の最後の要素で、ヒープの上部に最大要素999を交換します。交換後、-7がヒープトップになります。 -7は順序付けられていないエリアの最大の要素ではないため、順序付けられていない領域の最大値89がヒープトップになるように、順序付けられていない領域を調整する必要があります。これにより、-7と89が交換されます。交換後、89の右のサブツリーは最大のヒープの特性を満たしていないため、右のサブツリーを最大のヒープに調整する必要があるため、下の図に示すように、-7は0と交換する必要があります。
図から、-7％89％スワップの場合、山の上部が最大の要素ですが、-7の左子は0で、右の子は-888です。 -7 <0であるため、ノード-7はヒープのプロパティを満たしていないため、調整する必要があります。したがって、0は-7と交換されます。
次に、順序付けられた領域になるまで2番目のステップを繰り返します。
最後に、得られるのは昇順のシーケンスです
4。時間の複雑さ
ヒープソートの時間は、主に初期ヒープを確立し、ヒープを繰り返し調整する時間のオーバーヘッドで構成されています。ヒープの並べ替えは不安定であるため、実際の状況に応じて取得する時間の複雑さは大きくなるため、平均時間の複雑さのみを取ることができます。
平均時間の複雑さは次のとおりです。O（n * log2（n））
ヒープソートの時間のかかる操作には、以下が含まれます。初期ヒープ +ヒープの繰り返し調整、および時間の複雑さは次のとおりです。
1.初期ヒープビルディング：各親ノードは、左右の子ノードと最大2回比較および交換するため、複雑さは親ノードの数に関連しています。 2x <= n（xは、n要素を半分に折り畳むことができる回数、つまり親ノードの数）に基づいて、x = log2nを取得します。つまり、o（log2n）
2。ヒープの繰り返し調整：ヒープの初期化中に配列比較結果が記録されるため、ヒープの種類は元のシーケンスの配列の順序に敏感ではなく、最良の状況は最悪の場合に似ています。ヒープトップ要素はn-1回抽出する必要があります。ヒープトップ要素を採取するたびに、ヒープを再構築する必要があります（O（Heapの再構築）<O（初期ヒープ））。したがって、o（n-1） * o（log2n）未満
推奨される使用法：
ヒープの初期化を比較する必要があるため、ヒープの並べ替えは、データボリュームが非常に大きい状況（百万データ以上）に適しています。効率的なクイックソートは再帰的実装に基づいているため、データボリュームが非常に大きいときにスタックオーバーフローエラーが発生します。
5。Javaサンプルコード
public class Heapsort {private static int [] sort = new int [] {1,0,10,20,3,5,6,4,9,8,12、17,34,11}; public static void main（string [] args）{buildmaxheapify（sort）; Heapsort（sort）; print（sort）; } private static void buildmaxheapify（int [] data）{//子供のない人のみが最大のヒープを作成する必要があり、最後の親ノードint startindex = getParentIndex（data.length-1）; //端から最大ヒープを作成します。 }}/***最大ヒープを作成***@paramdata*@paramheapsizeには、最大値は一般的に使用されます。最大値は端に配置されているため、最大ヒープ*@paramindexは、最大ヒープが現在必要な位置に分類されなくなりました*/static maxheapify（int int int int [int] ems the heapsize in the heapsize（左および右の子供ノードint left = getChildLeftIndex（index）; int right = getChildRightIndex（index）; int ariggest = index; if（left <heapsize && data [index] <data [left]）{olagest = left; } if（right <heapsize && data [ragesgest] <data [right]）{rigast = right; } //最大値を取得した後、交換する必要がある場合があります。交換した場合、その子供は最大の山ではないかもしれません。 （最大！= index）{int temp = data [index];の場合、再調整する必要があります。 data [index] = data [最大];データ[最大] =温度; maxheapify（データ、豪華、最大）; }} /***ソート、最大値は最後に配置されます。データは最大のヒープですが、 * * *@paramdata */private static void heapsort（int [] data）{//最後にヘッダーと交換すると、（int i = data.length-1; i> 0; i-）{int temp = data [0]; data [0] = data [i]; data [i] = temp; maxheapify（data、i、0）; }} / ** *paramcurrent *@return * / private static int getParentIndex（int current）{return（current-1）>> 1; } / ** *現在の子ノードの位置括弧に注意を払うと、追加の優先順位は高くなります * *@paramcurrent *@return * / private static int getChildLeftIndex（int current）{return（current << 1）+1; } / ** *右子ノード位置 * *@paramcurrent *@return * / private static int getChildRightIndex（int current）{return（current << 1）+2; } private static void print（int [] data）{int pre = -2; for（int i = 0; i <data.length; i ++）{if（pre <（int）getLog（i+1））{pre =（int）getLog（i+1）; System.out.println（）; } system.out.print（data [i]+"|"）; }}/** *base 2 * *@paraparam *@return */private static double getlog（double param）{return math.log（param）/math.log（2）; }}