1. 不得不說說二叉樹
要了解堆首先得了解一下二叉樹，在計算機科學(xué)中，二叉樹是每個節(jié)點最多有兩個子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實現(xiàn)二叉查找樹和二叉堆。
二叉樹的每個結(jié)點至多只有二棵子樹（不存在度大于 2 的結(jié)點），二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第 i 層至多有 2i - 1 個結(jié)點；深度為 k 的二叉樹至多有 2k - 1 個結(jié)點；對任何一棵二叉樹 T，如果其終端結(jié)點數(shù)為 n0，度為 2 的結(jié)點數(shù)為 n2，則n0 = n2 + 1。
樹和二叉樹的三個主要差別：
樹的結(jié)點個數(shù)至少為 1，而二叉樹的結(jié)點個數(shù)可以為 0
樹中結(jié)點的最大度數(shù)沒有限制，而二叉樹結(jié)點的最大度數(shù)為 2
樹的結(jié)點無左、右之分，而二叉樹的結(jié)點有左、右之分
二叉樹又分為完全二叉樹（complete binary tree）和滿二叉樹（full binary tree）
滿二叉樹：一棵深度為 k，且有 2k - 1 個節(jié)點稱之為滿二叉樹

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

（深度為 3 的完全二叉樹 complete binary tree）
2. 什么是堆？
堆（二叉堆）可以視為一棵完全的二叉樹，完全二叉樹的一個“優(yōu)秀”的性質(zhì)是，除了最底層之外，每一層都是滿的，這使得堆可以利用數(shù)組來表示（普通的一般的二叉樹通常用鏈表作為基本容器表示），每一個結(jié)點對應(yīng)數(shù)組中的一個元素。
如下圖，是一個堆和數(shù)組的相互關(guān)系

（堆和數(shù)組的相互關(guān)系）
對于給定的某個結(jié)點的下標(biāo) i，可以很容易的計算出這個結(jié)點的父結(jié)點、孩子結(jié)點的下標(biāo)：
Parent(i) = floor(i/2)，i 的父節(jié)點下標(biāo)
Left(i) = 2i，i 的左子節(jié)點下標(biāo)
Right(i) = 2i + 1，i 的右子節(jié)點下標(biāo)

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

（最大堆）
最小堆：
最小堆中的最小元素值出現(xiàn)在根結(jié)點（堆頂）
堆中每個父節(jié)點的元素值都小于等于其孩子結(jié)點（如果存在）

（最小堆）
3. 堆排序原理
堆排序就是把最大堆堆頂?shù)淖畲髷?shù)取出，將剩余的堆繼續(xù)調(diào)整為最大堆，再次將堆頂?shù)淖畲髷?shù)取出，這個過程持續(xù)到剩余數(shù)只有一個時結(jié)束。在堆中定義以下幾種操作：
最大堆調(diào)整（Max-Heapify）：將堆的末端子節(jié)點作調(diào)整，使得子節(jié)點永遠小于父節(jié)點
創(chuàng)建最大堆（Build-Max-Heap）：將堆所有數(shù)據(jù)重新排序，使其成為最大堆
堆排序（Heap-Sort）：移除位在第一個數(shù)據(jù)的根節(jié)點，并做最大堆調(diào)整的遞歸運算
繼續(xù)進行下面的討論前，需要注意的一個問題是：數(shù)組都是 Zero-Based，這就意味著我們的堆數(shù)據(jù)結(jié)構(gòu)模型要發(fā)生改變

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

（Max-Heapify）
由于一次調(diào)整后，堆仍然違反堆性質(zhì)，所以需要遞歸的測試，使得整個堆都滿足堆性質(zhì)，用 JavaScript 可以表示如下：

/**
 * 從 index 開始檢查并保持最大堆性質(zhì)
 *
 * @array
 *
 * @index 檢查的起始下標(biāo)
 *
 * @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); // 遞歸調(diào)整
 }
}

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

通常來說，遞歸主要用在分治法中，而這里并不需要分治。而且遞歸調(diào)用需要壓棧/清棧，和迭代相比，性能上有略微的劣勢。當(dāng)然，按照20/80法則，這是可以忽略的。但是如果你覺得用遞歸會讓自己心里過不去的話，也可以用迭代，比如下面這樣：

/**
 * 從 index 開始檢查并保持最大堆性質(zhì)
 *
 * @array
 *
 * @index 檢查的起始下標(biāo)
 *
 * @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;
}

創(chuàng)建最大堆（Build-Max-Heap）的作用是將一個數(shù)組改造成一個最大堆，接受數(shù)組和堆大小兩個參數(shù)，Build-Max-Heap 將自下而上的調(diào)用 Max-Heapify 來改造數(shù)組，建立最大堆。因為 Max-Heapify 能夠保證下標(biāo) i 的結(jié)點之后結(jié)點都滿足最大堆的性質(zhì)，所以自下而上的調(diào)用 Max-Heapify 能夠在改造過程中保持這一性質(zhì)。如果最大堆的數(shù)量元素是 n，那么 Build-Max-Heap 從 Parent(n) 開始，往上依次調(diào)用 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先調(diào)用Build-Max-Heap將數(shù)組改造為最大堆，然后將堆頂和堆底元素交換，之后將底部上升，最后重新調(diào)用Max-Heapify保持最大堆性質(zhì)。由于堆頂元素必然是堆中最大的元素，所以一次操作之后，堆中存在的最大元素被分離出堆，重復(fù)n-1次之后，數(shù)組排列完畢。整個流程如下：

用 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 語言實現(xiàn)
最后，把上面的整理為完整的 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）算法性能/復(fù)雜度
堆排序的時間復(fù)雜度非常穩(wěn)定（我們可以看到，對輸入數(shù)據(jù)不敏感），為O(n㏒n)復(fù)雜度，最好情況與最壞情況一樣。
但是，其空間復(fù)雜度依實現(xiàn)不同而不同。上面即討論了兩種常見的復(fù)雜度：O(n)與O(1)。本著節(jié)約空間的原則，我推薦O(1)復(fù)雜度的方法。

（2）算法穩(wěn)定性
堆排序存在大量的篩選和移動過程，屬于不穩(wěn)定的排序算法。

（3）算法適用場景
堆排序在建立堆和調(diào)整堆的過程中會產(chǎn)生比較大的開銷，在元素少的時候并不適用。但是，在元素比較多的情況下，還是不錯的一個選擇。尤其是在解決諸如“前n大的數(shù)”一類問題時，幾乎是首選算法。

最新評論