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

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

引入堆

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

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

堆可以非常高效方便的解決很多問(wèn)題，比如說(shuō)：

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

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

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

說(shuō)了這么多好處，堆到底是什么呢？

堆的概念

完全二叉樹

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

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


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


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

編號(hào)與數(shù)組存儲(chǔ)

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