計算機程序的思維邏輯 (45) - 神奇的堆

前面幾節(jié)介紹了Java中的基本容器類，每個容器類背后都有一種數(shù)據(jù)結(jié)構(gòu)，ArrayList是動態(tài)數(shù)組，LinkedList是鏈表，HashMap/HashSet是哈希表，TreeMap/TreeSet是紅黑樹，本節(jié)介紹另一種數(shù)據(jù)結(jié)構(gòu) - 堆。

引入堆

之前我們提到過堆，那里，堆指的是內(nèi)存中的區(qū)域，保存動態(tài)分配的對象，與棧相對應(yīng)。這里的堆是一種數(shù)據(jù)結(jié)構(gòu)，與內(nèi)存區(qū)域和分配無關(guān)。

堆是什么結(jié)構(gòu)呢？這個我們待會再細看。我們先來說明，堆有什么用？為什么要介紹它？

堆可以非常高效方便的解決很多問題，比如說：

  • 優(yōu)先級隊列，我們之前介紹的隊列實現(xiàn)類LinkedList是按添加順序排隊的，但現(xiàn)實中，經(jīng)常需要按優(yōu)先級來，每次都應(yīng)該處理當前隊列中優(yōu)先級最高的，高優(yōu)先級的，即使來得晚，也應(yīng)該被優(yōu)先處理。
  • 求前K個最大的元素，元素個數(shù)不確定，數(shù)據(jù)量可能很大，甚至源源不斷到來，但需要知道到目前為止的最大的前K個元素。這個問題的變體有：求前K個最小的元素，求第K個最大的，求第K個最小的。
  • 求中值元素，中值不是平均值，而是排序后中間那個元素的值，同樣，數(shù)據(jù)量可能很大，甚至源源不斷到來。

堆還可以實現(xiàn)排序，稱之為堆排序，不過有比它更好的排序算法，所以，我們就不介紹其在排序中的應(yīng)用了。

Java容器中有一個類PriorityQueue，就表示優(yōu)先級隊列，它實現(xiàn)了堆，下節(jié)我們會詳細介紹。關(guān)于后面兩個問題，它們是如何使用堆高效解決的，我們會在接下來的幾節(jié)中用代碼實現(xiàn)并詳細解釋。

說了這么多好處，堆到底是什么呢？

堆的概念

完全二叉樹

堆首先是一顆二叉樹，但它是完全二叉樹。什么是完全二叉樹呢？我們先來看另一個相似的概念，滿二叉樹。

滿二叉樹是指，除了最后一層外，每個節(jié)點都有兩個孩子，而最后一層都是葉子節(jié)點，都沒有孩子。比如，下圖兩個二叉樹都是滿二叉樹。


滿二叉樹一定是完全二叉樹，但完全二叉樹不要求最后一層是滿的，但如果不滿，則要求所有節(jié)點必須集中在最左邊，從左到右是連續(xù)的，中間不能有空的。比如說，下面幾個二叉樹都是完全二叉樹：


而下面的這幾個則都不是完全二叉樹：

編號與數(shù)組存儲

在完全二叉樹中，可以給每個節(jié)點一個編號，編號從1開始連續(xù)遞增，從上到