（4）堆排序 (Heap Sort)

2018-04-18 16:04 更新

算法原理

先上一張堆排序動(dòng)畫(huà)演示圖片：

圖片來(lái)自維基百科
圖片來(lái)自維基百科

1. 不得不說(shuō)說(shuō)二叉樹(shù)

要了解堆首先得了解一下二叉樹(shù)，在計(jì)算機(jī)科學(xué)中，二叉樹(shù)是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹(shù)的樹(shù)結(jié)構(gòu)。通常子樹(shù)被稱(chēng)作“左子樹(shù)”（left subtree）和“右子樹(shù)”（right subtree）。二叉樹(shù)常被用于實(shí)現(xiàn)二叉查找樹(shù)和二叉堆。

二叉樹(shù)的每個(gè)結(jié)點(diǎn)至多只有二棵子樹(shù)（不存在度大于 2 的結(jié)點(diǎn)），二叉樹(shù)的子樹(shù)有左右之分，次序不能顛倒。


在二叉樹(shù)的第i層至多有20150904215445580個(gè)結(jié)點(diǎn)

深度為K的二叉樹(shù)的最大節(jié)點(diǎn)數(shù)為(k>=1)

20150904220459657

對(duì)于任何終端結(jié)點(diǎn) 20150904221345964 ，度為2的節(jié)點(diǎn)數(shù)為 20150904221441164 ，則 20150904221345964 = 20150904221441164 + 1 


樹(shù)和二叉樹(shù)的三個(gè)主要差別：

  • 樹(shù)的結(jié)點(diǎn)個(gè)數(shù)至少為 1，而二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)可以為 0
  • 樹(shù)中結(jié)點(diǎn)的最大度數(shù)沒(méi)有限制，而二叉樹(shù)結(jié)點(diǎn)的最大度數(shù)為 2
  • 樹(shù)的結(jié)點(diǎn)無(wú)左、右之分，而二叉樹(shù)的結(jié)點(diǎn)有左、右之分

二叉樹(shù)又分為完全二叉樹(shù)（complete binary tree）和滿(mǎn)二叉樹(shù)（full binary tree）

滿(mǎn)二叉樹(shù)：一棵深度為 k，且有 2k - 1 個(gè)節(jié)點(diǎn)稱(chēng)之為滿(mǎn)二叉樹(shù)

深度為 3 的滿(mǎn)二叉樹(shù) full binary tree
深度為 3 的滿(mǎn)二叉樹(shù) full binary tree

完全二叉樹(shù)：深度為 k，有 n 個(gè)節(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)節(jié)點(diǎn)都與深度為 k 的滿(mǎn)二叉樹(shù)中序號(hào)為 1 至 n 的節(jié)點(diǎn)對(duì)應(yīng)時(shí)，稱(chēng)之為完全二叉樹(shù)

深度為 3 的完全二叉樹(shù) complete binary tree
深度為 3 的完全二叉樹(shù) complete binary tree

2. 什么是堆？

堆（二叉堆）可以視為一棵完全的二叉樹(shù)，完全二叉樹(shù)的一個(gè)“優(yōu)秀”的性質(zhì)是，除了最底層之外，每一層都是滿(mǎn)的，這使得堆可以利用數(shù)組來(lái)表示（普通的一般的二叉樹(shù)通常用鏈表作為基本容器表示），每一個(gè)結(jié)點(diǎn)對(duì)應(yīng)數(shù)組中的一個(gè)元素。

如下圖，是一個(gè)堆和數(shù)組的相互關(guān)系

堆和數(shù)組的相互關(guān)系
堆和數(shù)組的相互關(guān)系

對(duì)于給定的某個(gè)結(jié)點(diǎn)的下標(biāo) i，可以很容易的計(jì)算出這個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)、孩子結(jié)點(diǎn)的下標(biāo)：

  • Parent(i) = floor(i/2)，i 的父節(jié)點(diǎn)下標(biāo)
  • Left(i) = 2i，i 的左子節(jié)點(diǎn)下標(biāo)
  • Right(i) = 2i + 1，i 的右子節(jié)點(diǎn)下標(biāo)

二叉堆一般分為兩種：最大堆和最小堆。

最大堆：

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

最大堆
最大堆

最小堆：

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

最小堆
最小堆

3. 堆排序原理

堆排序就是把最大堆堆頂?shù)淖畲髷?shù)取出，將剩余的堆繼續(xù)調(diào)整為最大堆，再次將堆頂?shù)淖畲髷?shù)取出，這個(gè)過(guò)程持續(xù)到剩余數(shù)只有一個(gè)時(shí)結(jié)束。在堆中定義以下幾種操作：

  • 最大堆調(diào)整（Max-Heapify）：將堆的末端子節(jié)點(diǎn)作調(diào)整，使得子節(jié)點(diǎn)永遠(yuǎn)小于父節(jié)點(diǎn)
  • 創(chuàng)建最大堆（Build-Max-Heap）：將堆所有數(shù)據(jù)重新排序，使其成為最大堆
  • 堆排序（Heap-Sort）：移除位在第一個(gè)數(shù)據(jù)的根節(jié)點(diǎn)，并做最大堆調(diào)整的遞歸運(yùn)算

繼續(xù)進(jìn)行下面的討論前，需要注意的一個(gè)問(wèn)題是：數(shù)組都是 Zero-Based，這就意味著我們的堆數(shù)據(jù)結(jié)構(gòu)模型要發(fā)生改變

Zero-BasedZero-Based

相應(yīng)的，幾個(gè)計(jì)算公式也要作出相應(yīng)調(diào)整：

  • Parent(i) = floor((i-1)/2)，i 的父節(jié)點(diǎn)下標(biāo)
  • Left(i) = 2i + 1，i 的左子節(jié)點(diǎn)下標(biāo)
  • Right(i) = 2(i + 1)，i 的右子節(jié)點(diǎn)下標(biāo)

最大堆調(diào)整（MAX‐HEAPIFY）的作用是保持最大堆的性質(zhì)，是創(chuàng)建最大堆的核心子程序，作用過(guò)程如圖所示：

Max-Heapify
Max-Heapify

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

/**
 * 從 index 開(kāi)始檢查并保持最大堆性質(zhì)
 *
 * @array
 *
 * @index 檢查的起始下標(biāo)
 *
 * @heapSize 堆大小
 *
 **/
function maxHeapify(array, index, heapSize) {
 var iMax = index,
 iLeft = 2 * index + 1,
 iRight = 2 * (index + 1);

 if (iLeft 
 iMax = iLeft;
 }

 if (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;
}

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

/**
 * 從 index 開(kāi)始檢查并保持最大堆性質(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 
 iMax = iLeft;
 }

 if (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）的作用是將一個(gè)數(shù)組改造成一個(gè)最大堆，接受數(shù)組和堆大小兩個(gè)參數(shù)，Build-Max-Heap 將自下而上的調(diào)用 Max-Heapify 來(lái)改造數(shù)組，建立最大堆。因?yàn)?Max-Heapify 能夠保證下標(biāo) i 的結(jié)點(diǎn)之后結(jié)點(diǎn)都滿(mǎn)足最大堆的性質(zhì)，所以自下而上的調(diào)用 Max-Heapify 能夠在改造過(guò)程中保持這一性質(zhì)。如果最大堆的數(shù)量元素是 n，那么 Build-Max-Heap 從 Parent(n) 開(kāi)始，往上依次調(diào)用 Max-Heapify。流程如下：

Build-Max-Heap
Build-Max-Heap

用 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ù)組排列完畢。整個(gè)流程如下：

Heap-Sort
Heap-Sort

用 JavaScript 描述如下：

function heapSort(array, heapSize) {

 buildMaxHeap(array, heapSize);

 for (int i = heapSize - 1; i > 0; i--) {
 swap(array, 0, i);
 maxHeapify(array, 0, i);
 } 
}

JavaScript 語(yǔ)言實(shí)現(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);
}

參考文章


以上內(nèi)容是否對(duì)您有幫助：
在線筆記
App下載
App下載

掃描二維碼

下載編程獅App

公眾號(hào)
微信公眾號(hào)

編程獅公眾號(hào)