DIV CSS 佈局教程網

 DIV+CSS佈局教程網 >> 網頁腳本 >> JavaScript入門知識 >> JavaScript基礎知識 >> 圖文詳解Heap Sort堆排序算法及JavaScript的代碼實現
圖文詳解Heap Sort堆排序算法及JavaScript的代碼實現
編輯: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 個節點稱之為滿二叉樹

201654180037749.png (325×199)

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

201654180205013.png (298×198)

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

201654180403849.png (564×182)

(堆和數組的相互關系)
對於給定的某個結點的下標 i,可以很容易的計算出這個結點的父結點、孩子結點的下標:
Parent(i) = floor(i/2),i 的父節點下標
Left(i) = 2i,i 的左子節點下標
Right(i) = 2i + 1,i 的右子節點下標

201654180531505.png (549×172)

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

201654180552874.png (373×112)

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

201654180607921.png (370×112)

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

201654180627211.png (562×194)

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

201654180644675.png (564×411)

(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。流程如下:

201654180758506.jpg (614×673)

用 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次之後,數組排列完畢。整個流程如下:

201654180823776.jpg (604×926)

用 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大的數”一類問題時,幾乎是首選算法。

XML學習教程| jQuery入門知識| AJAX入門| Dreamweaver教程| Fireworks入門知識| SEO技巧| SEO優化集錦|
Copyright © DIV+CSS佈局教程網 All Rights Reserved