圖文詳解Heap Sort堆排序演算法及JavaScript的程式碼實作_基礎知識

1. 不得不說說二元樹
要了解堆首先得了解二叉樹，在電腦科學中，二元樹是每個節點最多有兩個子樹的樹結構。通常子樹被稱為「左子樹」（left subtree）和「右子樹」（right subtree）。二元樹常被用來實現二元查找樹和二元堆。
二元樹的每個結點至多只有二棵子樹（不存在度大於 2 的結點），二叉樹的子樹有左右之分，次序不能顛倒。二元樹的第i 層至多有2i - 1 個結點；深度為k 的二元樹至多有2k - 1 個結點；對任何一棵二元樹T，如果其終端結點數為n0，度為2 的結點數為n2，則n0 = n2 + 1。
樹和二元樹的三個主要差異：
樹的結點個數至少為 1，而二元樹的結點數量可以是 0
樹中結點的最大度數沒有限制，而二元樹結點的最大度數為 2
樹的結點無左、右之分，而二元樹的結點有左、右之分
二元樹又分為完全二元樹（complete binary tree）和滿二元樹（full binary tree）
滿叉樹：一棵深度為 k，且有 2k - 1 個節點稱為滿叉樹

（深度為 3 的滿叉樹 full binary tree）
完全二元樹：深度為 k，有 n 個節點的二元樹，當且僅當其每一個節點都與深度為 k 的滿二叉樹中序號為 1 至 n 的節點對應時，稱之為完全二叉樹

（深度為 3 的完全二元樹 complete binary tree）
2. 什麼是堆？
堆（二元堆）可以視為一棵完全的二元樹，完全二元樹的一個「優秀」的性質是，除了最底層之外，每一層都是滿的，這使得堆可以利用數組來表示（普通的一般的二元樹通常以鍊錶作為基本容器表示），每一個結點對應數組中的一個元素。
如下圖，是一個堆和數組的相互關係

（堆和陣列的相互關係）
對於給定的某個結點的下標 i，可以很容易的計算出這個結點的父結點、孩子結點的下標：
Parent(i) = floor(i/2)，i 的父節點下標
Left(i) = 2i，i 的左子節點下標
Right(i) = 2i + 1，i 的右子節點下標

二元堆一般分為兩種：最大堆和最小堆。
最大堆：
最大堆中的最大元素值出現在根結點（堆頂）
堆中每個父節點的元素值都大於等於其孩子結點（如果存在）

（最大堆）
最小堆：
最小堆中的最小元素值出現在根結點（堆頂）
堆中每個父節點的元素值都小於等於其孩子結點（如果存在）

（最小堆）
3. 堆排序原理
堆排序就是把最大堆堆頂的最大數取出，將剩餘的堆繼續調整為最大堆，再次將堆頂的最大數取出，這個過程持續到剩餘數只有一個時結束。在堆中定義以下幾個操作：
最大堆調整（Max-Heapify）：將堆的末端子節點作調整，使得子節點永遠小於父節點
建立最大堆（Build-Max-Heap）：將堆所有資料重新排序，使其成為最大堆
堆排序（Heap-Sort）：移除位元在第一個資料的根節點，並做最大堆調整的遞歸運算
在繼續進行下面的討論之前，需要注意的一個問題是：數組都是 Zero-Based，這意味著我們的堆資料結構模型要改變

（Zero-Based）
對應的，幾個計算公式也要做出相應調整：
Parent(i) = floor((i-1)/2)，i 的父節點下標
Left(i) = 2i + 1，i 的左子節點下標
Right(i) = 2(i + 1)，i 的右子節點下標
最大堆調整（MAX‐HEAPIFY）的作用是保持最大堆的性質，是創建最大堆的核心子程序，作用過程如圖所示：

(Max-Heapify)
1 回の調整後もヒープはヒープ プロパティに違反しているため、ヒープ全体がヒープ プロパティを満たすようにするために再帰的テストが必要です。これは 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) は、配列を最大ヒープに変換することです。配列とヒープ サイズの 2 つのパラメーターを受け取ります。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 を呼び出して、最大ヒープ プロパティを維持します。ヒープの先頭要素はヒープ内で最大の要素でなければならないため、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];
  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) の計算量です。 ただし、その空間の複雑さは実装ごとに異なります。 2 つの一般的な複雑さ、O(n) と O(1) については上で説明しました。スペースを節約するという原則に従って、O(1) 複雑さの方法をお勧めします。

(2) アルゴリズムの安定性
ヒープソートには多数のスクリーニングと移動プロセスが含まれ、不安定なソートアルゴリズムです。

(3) アルゴリズム適用シナリオ
ヒープのソートは、ヒープの確立と調整のプロセスで比較的大きなオーバーヘッドを引き起こすため、要素が少ない場合には適していません。ただし、要素がたくさんある場合には、それでも良い選択です。特に、「最初の n 個の最大数」などの問題を解く場合、ほぼ推奨されるアルゴリズムです。