Heap Sort ヒープソートアルゴリズムとJavaScriptコード実装を図解で詳しく解説_基礎知識

1. 二分木について話さなければなりません
ヒープを理解するには、まずバイナリ ツリーを理解する必要があります。コンピュータ サイエンスでは、バイナリ ツリーは各ノードが最大 2 つのサブツリーを持つツリー構造です。通常、サブツリーは「左サブツリー」および「右サブツリー」と呼ばれます。バイナリ ツリーは、バイナリ検索ツリーとバイナリ ヒープの実装によく使用されます。
バイナリ ツリーの各ノードには最大 2 つのサブツリーがあります (次数が 2 を超えるノードはありません)。バイナリ ツリーのサブツリーは左右のサブツリーに分割され、順序を逆にすることはできません。バイナリ ツリーの i 番目のレベルには最大 2i - 1 個のノードがあり、深さ k のバイナリ ツリーには、ターミナル ノードの数が n0 の場合、最大で 2k - 1 個のノードがあります。次数 2 の場合は n2 となり、n0 = n2 + 1 となります。
ツリーとバイナリ ツリーの 3 つの主な違い:
ツリーのノード数は少なくとも 1 でなければなりませんが、バイナリ ツリーのノード数は 0 であっても構いません
ツリー内のノードの最大次数に制限はありませんが、バイナリ ツリー内のノードの最大次数は 2
木のノードは左右に分割されていませんが、二分木のノードは左右に分割されています
バイナリ ツリーは、完全バイナリ ツリーと完全バイナリ ツリーに分類されます
完全なバイナリ ツリー: 深さ k および 2k - 1 ノードを持つツリーは完全なバイナリ ツリーと呼ばれます

(深さ 3 の完全なバイナリ ツリー)
完全な二分木: 深さ k でノードが n の二分木。その各ノードが深さ k の完全な二分木で 1 から n の番号が付けられたノードに対応する場合に限り、完全な二分木と呼ばれます
。

(深さ 3 の完全なバイナリ ツリー)
2. ヒープとは何ですか?
ヒープ (バイナリ ヒープ) は完全なバイナリ ツリーと見なすことができます。完全なバイナリ ツリーの「優れた」特性は、最下位レベルを除くすべてのレベルが満杯であることです。これにより、ヒープは配列を使用して表現できるようになります。バイナリ ツリーは通常、基本コンテナとしてリンクされたリストによって表され、各ノードは配列内の要素に対応します。
以下に示すように、ヒープと配列の関係です

(ヒープと配列の相互関係)
ノードの指定された添字 i について、このノードの親ノードと子ノードの添字は簡単に計算できます。
Parent(i) = Floor(i/2)、i の親ノードの添字
Left(i) = 2i、i の左添え字
Right(i) = 2i + 1、i の右側の子ノードの添字

バイナリ ヒープは、通常、最大ヒープと最小ヒープの 2 つのタイプに分類されます。
最大ヒープ:
最大ヒープ内の最大要素値はルート ノード (ヒープの最上位) に表示されます
ヒープ内の各親ノードの要素値は、その子ノード (存在する場合) 以上です

(最大ヒープ)
最小ヒープ:
最小ヒープ内の最小要素値はルート ノード (ヒープの最上部) に表示されます
ヒープ内の各親ノードの要素値は、その子ノード (存在する場合) 以下です

(最小ヒープ)
3. ヒープソートの原則
ヒープソートとは、最大ヒープの先頭の最大数を取り出し、残りのヒープを最大ヒープに合わせて調整し、再びヒープの先頭の最大数を取り出すという処理です。残りの番号は 1 つだけです。ヒープ上で次の操作を定義します:
Max-Heapify: 子ノードが常に親ノードよりも小さくなるように、ヒープの最後の子ノードを調整します
最大ヒープの作成 (Build-Max-Heap): ヒープ内のすべてのデータを並べ替えて最大ヒープにします
ヒープソート: 最初のデータのルートノードを削除し、最大ヒープ調整の再帰操作を実行します
以下の説明を続ける前に、配列はすべてゼロベースであることに注意する必要があります。これは、ヒープ データ構造モデルが変更されることを意味します

（ゼロベース）
これに応じて、いくつかの計算式もそれに応じて調整する必要があります:
Parent(i) = Floor((i-1)/2)、i の親ノードの添字
Left(i) = 2i + 1、i
の左の子ノードの添え字 Right(i) = 2(i + 1)、i の右側の子ノードの添字
最大ヒープ調整 (MAX-HEAPIFY) の機能は、最大ヒープのプロパティを維持することであり、最大ヒープを作成するためのコア サブルーチンです。関数の処理は図に示すとおりです。

（Max-Heapify）
由於一次調整後，堆仍然違反堆性質，所以需要遞歸的測試，使得整個堆都滿足堆性質，用 JavaScript 可以表示如下：

/**
 * 从 index 开始检查并保持最大堆性质
 *
 * @array
 *
 * @index 检查的起始下标
 *
 * @heapSize 堆大小
 *
 **/
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(array, iMax, heapSize); // 递归调整
 }
}

function swap(array, i, j) {
 var temp = array[i];
 array[i] = array[j];
 array[j] = temp;
}

通常來說，遞迴主要用在分治法中，而這裡並不需要分治。而且遞歸呼叫需要壓棧/清棧，和迭代相比，效能上有略微的劣勢。當然，依照20/80法則，這是可以忽略的。但如果你覺得用遞迴會讓自己心裡過不去的話，也可以用迭代，例如下面這樣：

/**
 * 从 index 开始检查并保持最大堆性质
 *
 * @array
 *
 * @index 检查的起始下标
 *
 * @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];
 array[i] = array[j];
 array[j] = temp;
}

創建最大堆（Build-Max-Heap）的作用是將一個數組改造成一個最大堆，接受數組和堆大小兩個參數，Build-Max-Heap 將自下而上的調用Max-Heapify 來改造數組，建立最大堆。因為 Max-Heapify 能夠保證下標 i 的結點之後結點都滿足最大堆的性質，所以自下而上的調用 Max-Heapify 能夠在改造過程中保持這一性質。如果最大堆的數量元素是 n，那麼 Build-Max-Heap 從 Parent(n) 開始，往上依序呼叫 Max-Heapify。流程如下：

用 JavaScript 描述如下：

function buildMaxHeap(array, heapSize) {
 var i,
   iParent = Math.floor((heapSize - 1) / 2);
   
 for (i = iParent; i >= 0; i--) {
  maxHeapify(array, i, heapSize);
 }
}

堆排序（Heap-Sort）是堆排序的介面演算法，Heap-Sort先呼叫Build-Max-Heap將陣列改造為最大堆，然後將堆頂和堆底元素交換，之後將底部上升，最後重新調用Max-Heapify保持最大堆性質。由於堆頂元素必然是堆中最大的元素，所以一次操作之後，堆中存在的最大元素被分離出堆，重複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];
  array[i] = array[j];
  array[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(n㏒n)複雜度，最好情況與最壞情況一樣。
但是，其空間複雜度依實現不同而不同。上面即討論了兩種常見的複雜度：O(n)與O(1)。本著節省空間的原則，我推薦O(1)複雜度的方法。

（2）演算法穩定性
堆排序存在大量的篩選和移動過程，屬於不穩定的排序演算法。

（3）演算法適用場景
堆排序在建立堆和調整堆的過程中會產生比較大的開銷，在元素少的時候並不適用。但是，在元素比較多的情況下，還是不錯的選擇。尤其是在解決諸如「前n大的數」一類問題時，幾乎是首選演算法。