1。バイナリツリーについて話さなければなりません
ヒープを理解するには、まずバイナリツリーを理解する必要があります。コンピューターサイエンスでは、バイナリツリーは、ノードごとに最大2つのサブツリーを持つツリー構造です。通常、サブツリーは「左サブツリー」と「右サブツリー」と呼ばれます。バイナリツリーは、バイナリ検索ツリーとバイナリヒープを実装するためによく使用されます。
バイナリツリーの各ノードには、最大2つのサブツリー（2度を超えるノード）があります。バイナリツリーのサブツリーは左右に分割でき、順序を逆にすることはできません。バイナリツリーのi番目の層には、最大2i -1ノードがあります。 kの深さを持つバイナリツリーには、最大2k -1ノードがあります。任意のバイナリツリーtの場合、端子ノードの数がN0であり、2度のノードの数はN2、n0 = n2 + 1です。
ツリーとバイナリツリーには3つの主な違いがあります。
ツリー内のノードの数は少なくとも1ですが、バイナリツリーのノードの数は0になります。
ツリー内のノードの最大程度に制限はありませんが、バイナリツリーのノードの最大程度は2です
ツリーのノードには左と右に違いはありませんが、バイナリツリーのノードには左と右に違いはありません。
バイナリツリーは、完全なバイナリツリーと完全なバイナリツリーに分かれています。
フルバイナリツリー：Kの深さと2K -1ノードのあるツリーは、完全なバイナリツリーと呼ばれます
（深さ3の完全なバイナリツリー3）
完全なバイナリツリー：深さkのnノードを持つバイナリツリー。それぞれのノードが、深さkの完全なバイナリツリーのシーケンス番号1からNのノードに対応する場合にのみ、完全なバイナリツリーと呼ばれます。
（深さ3の完全なバイナリツリー3）
2。ヒープとは何ですか？
ヒープ（バイナリヒープ）は、完全なバイナリツリーと見なすことができます。完全なバイナリツリーの「優れた」プロパティは、下層を除いて、各レイヤーがいっぱいであり、ヒープを配列で表すことができるということです（通常の一般的なバイナリツリーは通常、リンクされたリストで基本容器として表されます）、各ノードはアレイの要素に対応します。
次の図は、ヒープとアレイの関係を示しています
（ヒープとアレイの関係）
ノードの指定された添え字Iの場合、このノードの親ノードと子ノードのサブスクリプトについて簡単に計算できます。
親（i）= floor（i/2）、iの親ノード添え付け
左（i）= 2i、iの左の子ノード添え付け
右（i）= 2i + 1、iの右の子ノード添え付け
通常、2種類のバイナリヒープには、最大のヒープと最小ヒープの2種類があります。
最大ヒープ：
最大ヒープの最大要素値は、ルートノード（ヒープの上部）に表示されます
ヒープ内の各親ノードの要素値は、子ノード以下の要素値（存在する場合）
（最大ヒープ）
最小ヒープ：
最小ヒープの最小要素値は、ルートノード（ヒープの上部）に表示されます
ヒープ内の各親ノードの要素値は、子ノード以下です（存在する場合）
（最小スタック）
3。ヒープソートの原理
ヒープの並べ替えは、最大ヒープの上部に最大数を取り出し、残りのヒープを最大ヒープに調整し続け、ヒープの上部に最大数を再び取り出すことです。このプロセスは、残りの数が1つしかなくなるまで続きます。ヒープ内の次の操作を定義します。
max-heapify：子ノードが常に親ノードよりも小さくなるように、ヒープのエンドノードを調整します
最大ヒープ（ビルドマックスヒープ）を作成する：ヒープのすべてのデータを並べ替えて最大ヒープにする
ヒープソート：最初のデータのルートノードを削除し、最大ヒープ調整の再帰操作を実行します
次の議論を継続する前に、注意する必要がある問題の1つは次のとおりです。配列はすべてゼロベースです。つまり、ヒープデータ構造モデルが変更されます。
（ゼロベース）
それに応じて、いくつかの計算式もそれに応じて調整する必要があります。
親（i）= floor（（i-1）/2）、iの親ノード添え付け
左（i）= 2i + 1、i
右（i）= 2（i + 1）、iの右の子ノード添え付け
Max Heap調整（Maxheapife）の機能は、最大のヒープの特性を維持することであり、最大のヒープを作成するためのコアサブルーチンです。動作プロセスを図に示します。
（Max-Heapify）
ヒープは1回の調整後もヒープの性質に違反しているため、ヒープ全体がヒープの性質を満たすように、再帰テストが必要です。次のようにJavaScriptで表現できます。
/** *インデックスからチェックして最大ヒーププロパティを維持 * * @Array * * @index check * * @heapsize heap size * **/function maxheapify（array、index、heapsize）{var imax = index、ileft = 2 * index + 1、iright = 2 *（index + 1）; if（ileft <heapsize && array [index] <array [ileft]）{imax = ileft; } if（iright <heapsize && array [imax] <array [iright]）{imax = iright; } if（imax！= index）{swap（array、imax、index）; maxheapify（配列、imax、Heapsize）; //再帰調整}} function swap（array、i、j）{var temp = array [i];配列[i] = array [j];配列[j] = temp;}一般的に、再帰は主に分裂と治療の方法で使用されており、ここでは分割と治療の必要はありません。さらに、再帰的な呼び出しには、スタックの押し/クリアリングが必要です。もちろん、これは20/80ルールに従って無視できます。しかし、再帰を使用することで不快感を覚えると思われる場合は、次のような反復を使用することもできます。
/** *インデックスからチェックして最大ヒーププロパティを維持 * * @Array * * @index checkの開始インデックス * * @heapsizeヒープサイズ * **/function maxheapify（array、index、heapsize）{var imax、ileft、iright; while（true）{imax = index; ileft = 2 * index + 1; iright = 2 *（index + 1）; if（ileft <heapsize && array [index] <array [ileft]）{imax = ileft; } if（iright <heapsize && array [imax] <array [iright]）{imax = iright; } if（imax！= index）{swap（array、imax、index）; index = imax; } else {break; }}} function swap（array、i、j）{var temp = array [i];配列[i] = array [j];配列[j] = temp;}最大ヒープ（ビルドマックスヒープ）を作成する目的は、配列を最大ヒープに変換し、アレイとヒープサイズの2つのパラメーターを受け入れることです。 Build-Max-Heapは、下からMax-Heapifyを呼び出してアレイを変換し、最大ヒープを構築します。 Max-Heapifyは、サブスクリプト後のノードが最大のヒープのプロパティを満たすことを保証できるため、Max-Heapifyへのボトムアップコールは、変換プロセス中にこのプロパティを維持できます。最大ヒープ番号要素がnの場合、ビルドマックスヒープは、親（n）から順番にmax-heapifyを呼び出します。プロセスは次のとおりです。
説明はJavaScriptで次のとおりです。
関数BuildMaxHeap（Array、Heapsize）{var i、iparent = math.floor（（Heapsize -1） / 2）; for（i = iparent; i> = 0; i-）{maxheapify（array、i、Heapsize）; }}ヒープソートは、ヒープソートのインターフェイスアルゴリズムです。ヒープソートの最初の最初の呼び出して、アレイを最大ヒープに変換して、ヒープの上部と下部要素を交換し、下部を上昇させ、最終的に最大のヒーププロパティを維持するためにMax-Heapifyを呼び出します。ヒープの上部要素はヒープの最大の要素でなければならないため、1回の操作の後、ヒープに存在する最大の要素はヒープからヒープから分離され、n-1回を繰り返した後、配列が配置されます。プロセス全体が次のとおりです。
説明はJavaScriptで次のとおりです。
function heapsort（array、Heapsize）{buildmaxheap（array、Heapsize）; for（int i = Heapsize-1; i> 0; i-）{swap（array、0、i）; maxheapify（array、0、i）; }}4。JavaScript言語実装
最後に、次のように上記を完全なJavaScriptコードに整理します。
function heapsort（array）{function swap（array、i、j）{var temp = array [i];配列[i] = array [j];配列[j] = temp; } function maxheapify（array、index、heapsize）{var imax、ileft、iright; while（true）{imax = index; ileft = 2 * index + 1; iright = 2 *（index + 1）; if（ileft <heapsize && array [index] <array [ileft]）{imax = ileft; } if（iright <heapsize && array [imax] <array [iright]）{imax = iright; } if（imax！= index）{swap（array、imax、index）; index = imax; } else {break; }}} function buildmaxheap（array）{var i、iparent = math.floor（array.length / 2）-1; for（i = iparent; i> = 0; i-）{maxheapify（array、i、array.length）; }} function sort（array）{buildmaxheap（array）; for（var i = array.length-1; i> 0; i-）{swap（array、0、i）; maxheapify（array、0、i）; } return array; } return sort（array）;}5。ヒープソーティングアルゴリズムの適用
（1）アルゴリズムのパフォーマンス/複雑さ
ヒープの種類の時間の複雑さは非常に安定しており（入力データに敏感ではないことがわかります）、O（nn）の複雑さ、最良のケースは最悪の場合と同じです。
ただし、その空間的な複雑さは実装によって異なります。上記では、2つの一般的な複雑さについて説明します：o（n）とo（1）。節約スペースの原則に基づいて、O（1）の複雑さの方法をお勧めします。
（2）アルゴリズムの安定性
不安定なソートアルゴリズムに属するヒープソートには、多数のフィルタリングプロセスと移動プロセスがあります。
（3）アルゴリズム適用シナリオ
ヒープの並べ替えは、ヒープを構築してヒープを調整する過程で比較的大きなオーバーヘッドが発生し、要素が少ない場合は適用できません。ただし、多くの要素がある場合、それはまだ良い選択です。特に、「上部Nの上部の数」などの問題を解決する場合、それはほぼ好ましいアルゴリズムです。