[[333346]]

什么是堆?

堆其實就是一種特殊的隊列——優(yōu)先隊列。

普通的隊列游戲規(guī)則很簡單：就是先進先出;但這種優(yōu)先隊列搞特殊，不是按照進隊列的時間順序，而是按照每個元素的優(yōu)先級來比拼，優(yōu)先級高的在堆頂。

這也很容易理解吧，比如各種軟件都有會員制度，某軟件用了會員就能加速下載的，不同等級的會員速度還不一樣，那就是優(yōu)先級不同呀。

還有其實每個人回復微信消息也是默默的把消息放進堆里排個序：先回男朋友女朋友的，然后再回其他人的。

這里要區(qū)別于操作系統(tǒng)里的那個“堆”，這兩個雖然都叫堆，但是沒有半毛錢關(guān)系，都是借用了 Heap 這個英文單詞而已。

 

我們再來回顧一下「堆」在整個 Java 集合框架中的位置：

 

也就是說，

• PriorityQueue 是一個類 (class);
• PriorityQueue 繼承自 Queue 這個接口 (Interface);

那 heap 在哪呢?

heap 其實是一個抽象的數(shù)據(jù)結(jié)構(gòu)，或者說是邏輯上的數(shù)據(jù)結(jié)構(gòu)，并不是一個物理上真實存在的數(shù)據(jù)結(jié)構(gòu)。

heap 其實有很多種實現(xiàn)方式，比如 binomial heap, Fibonacci heap 等等。但是面試最?？嫉?，也是最經(jīng)典的，就是 binary heap 二叉堆，也就是用一棵完全二叉樹來實現(xiàn)的。

那完全二叉樹是怎么實現(xiàn)的?

其實是用數(shù)組來實現(xiàn)的!

所以 binary heap/PriorityQueue 實際上是用數(shù)組來實現(xiàn)的。

這個數(shù)組的排列方式有點特別，因為它總會維護你定義的(或者默認的)優(yōu)先級最高的元素在數(shù)組的首位，所以不是隨便一個數(shù)組都叫「堆」，實際上，它在你心里，應該是一棵「完全二叉樹」。

這棵完全二叉樹，只存在你心里和各大書本上;實際在在內(nèi)存里，哪有什么樹?就是數(shù)組罷了。

那為什么完全二叉樹可以用數(shù)組來實現(xiàn)?是不是所有的樹都能用數(shù)組來實現(xiàn)?

這個就涉及完全二叉樹的性質(zhì)了，我們下一篇會細講，簡單來說，因為完全二叉樹的定義要求了它在層序遍歷的時候沒有氣泡，也就是連續(xù)存儲的，所以可以用數(shù)組來存放;第二個問題當然是否。

堆的特點

1.堆是一棵完全二叉樹;

2.堆序性 (heap order): 任意節(jié)點都優(yōu)于它的所有孩子。

a. 如果是任意節(jié)點都大于它的所有孩子，這樣的堆叫大頂堆，Max Heap;

b. 如果是任意節(jié)點都小于它的所有孩子，這樣的堆叫小頂堆，Min Heap

 

左圖是小頂堆，可以看出對于每個節(jié)點來說，都是小于它的所有孩子的，注意是所有孩子，包括孫子，曾孫...

3.既然堆是用數(shù)組來實現(xiàn)的，那么我們可以找到每個節(jié)點和它的父母/孩子之間的關(guān)系，從而可以直接訪問到它們。

 

比如對于節(jié)點 3 來說，

• 它的 Index = 1，
• 它的 parent index = 0,
• 左孩子 left child index = 3,
• 右孩子 right child index = 4.

可以歸納出如下規(guī)律：

• 設當前節(jié)點的 index = x,
• 那么 parent index = (x-1)/2,
• 左孩子 left child index = 2*x + 1,
• 右孩子 right child index = 2*x + 2.

有些書上可能寫法稍有不同，是因為它們的數(shù)組是從 1 開始的，而我這里數(shù)組的下標是從 0 開始的，都是可以的。

這樣就可以從任意一個點，一步找到它的孫子、曾孫子，真的太方便了，在后文講具體操作時大家可以更深刻的體會到。

基本操作

任何一個數(shù)據(jù)結(jié)構(gòu)，無非就是增刪改查四大類：

功能	方法	時間復雜度
增	offer(E e)	O(logn)
刪	poll()	O(logn)
改	無直接的 API	刪 + 增
查	peek()	O(1)

這里 peek() 的時間復雜度很好理解，因為堆的用途就是能夠快速的拿到一組數(shù)據(jù)里的最大/最小值，所以這一步的時間復雜度一定是 O(1) 的，這就是堆的意義所在。

那么我們具體來看 offer(E e) 和 poll() 的過程。

offer(E e)

比如我們新加一個 0 到剛才這個最小堆里面：

 

那很明顯，0 是要放在最上面的，可是，直接放上去就不是一棵完全二叉樹了啊。。

所以說，

• 我們先保證加了元素之后這棵樹還是一棵完全二叉樹，
• 然后再通過 swap 的方式進行微調(diào)，來滿足堆序性。

這樣就保證滿足了堆的兩個特點，也就是保證了加入新元素之后它還是個堆。

那具體怎么做呢：

Step 1.

先把 0 放在最后接上，別一上來就想著上位;

 

OK!總算先上岸了，然后我們再一步步往上走。

這里「能否往上走」的標準在于：

是否滿足堆序性。

也就是說，現(xiàn)在 5 和 0 之間不滿足堆序性，那么交換位置，換到直到滿足堆序性為止。

這里對于最小堆來說的堆序性，就是小的數(shù)要在上面。

Step 2. 與 5 交換

 

此時 0 和 3 不滿足堆序性了，那么再交換。

Step 3. 與 3 交換

 

還不行，0 還比 1 小，所以繼續(xù)換。

Step 4. 與 1 交換

 

OK!這樣就換好了，一個新的堆誕生了～

總結(jié)一下這個方法：

先把新元素加入數(shù)組的末尾，再通過不斷比較與 parent 的值的大小，決定是否交換，直到滿足堆序性為止。

這個過程就是 siftUp()，源碼如下：

 

 

 

 

時間復雜度

這里不難發(fā)現(xiàn)，其實我們只交換了一條支路上的元素，

 

也就是最多交換 O(height) 次。

那么對于完全二叉樹來說，除了最后一層都是滿的，O(height) = O(logn)。

所以 offer(E e) 的時間復雜度就是 O(logn) 啦。

poll()

poll() 就是把最頂端的元素拿走。

對了，沒有辦法拿走中間的元素，畢竟要 VIP 先出去，小弟才能出去。

那么最頂端元素拿走后，這個位置就空了：

 

我們還是先來滿足堆序性，因為比較容易滿足嘛，直接從最后面拿一個來補上就好了，先放個傀儡上來。

Step1. 末尾元素上位

 

這樣一來，堆序性又不滿足了，開始交換元素。

那 8 比 7 和 3 都大，應該和誰交換呢?

假設與 7 交換，那么 7 還是比 3 大，還得 7 和 3 換，麻煩。

所以是與左右孩子中較小的那個交換。

Step 2. 與 3 交換

 

下去之后，還比 5 和 4 大，那再和 4 換一下。

Step 3. 與 4 交換

 

OK!這樣這棵樹總算是穩(wěn)定了。

總結(jié)一下這個方法：

先把數(shù)組的末位元素加到頂端，再通過不斷比較與左右孩子的值的大小，決定是否交換，直到滿足堆序性為止。

這個過程就是 siftDown()，源碼如下：

 

時間復雜度

同樣道理，也只交換了一條支路上的元素，也就是最多交換 O(height) 次。

所以 offer(E e) 的時間復雜度就是 O(logn) 啦。

heapify()

還有一個大名鼎鼎的非常重要的操作，就是 heapify() 了，它是一個很神奇的操作，

可以用 O(n) 的時間把一個亂序的數(shù)組變成一個 heap。

但是呢，heapify() 并不是一個 public API，看：

 

所以我們沒有辦法直接使用。

唯一使用 heapify() 的方式呢，就是使用PriorityQueue(Collection c)

這個 constructor 的時候，人家會自動調(diào)用 heapify() 這個操作。

那具體是怎么做的呢?

哈哈源碼已經(jīng)暴露了：

從最后一個非葉子節(jié)點開始，從后往前做 siftDown().

因為葉子節(jié)點沒必要操作嘛，已經(jīng)到了最下面了，還能和誰 swap?

舉個例子：

 

我們想把這個數(shù)組進行 heapify() 操作，想把它變成一個最小堆，拿到它的最小值。

那就要從 3 開始，對 3，7，5進行 siftDown().

Step 1.

 

尷尬 😅，3 并不用交換，因為以它為頂點的這棵小樹已經(jīng)滿足了堆序性。

Step 2.

 

7 比它的兩個孩子都要大，所以和較小的那個交換一下。

交換完成后;

 

Step 3.

最后一個要處理的就是 5 了，那這里 5 比它的兩個孩子都要大，所以也和較小的那個交換一下。

 

換完之后結(jié)果如下，注意并沒有滿足堆序性，因為 4 還比 5 小呢。

 

所以接著和 4 換，結(jié)果如下：

 

這樣整個 heapify() 的過程就完成了。

好了難點來了，為什么時間復雜度是 O(n) 的呢?

怎么計算這個時間復雜度呢?

其實我們在這個過程里做的操作無非就是交換交換。

那到底交換了多少次呢?

沒錯，交換了多少次，時間復雜度就是多少。

那我們可以看出來，其實同一層的節(jié)點最多交換的次數(shù)都是相同的。

那么這個總的交換次數(shù) = 每層的節(jié)點數(shù) * 每個節(jié)點最多交換的次數(shù)

 

這里設 k 為層數(shù)，那么這個例子里 k=3.

 

所以 heapify() 時間復雜度是 O(n).

 

以上就是堆的三大重要操作，最后一個 heapify() 雖然不能直接操作，但是堆排序中用到了這種思路，之前的「選擇排序」那篇文章里也提到了一些，感興趣的同學可以后臺回復「選擇排序」獲得文章～至于堆排序的具體實現(xiàn)和應用，以及為什么實際生產(chǎn)中并不愛用它，我們之后再講。

最后再說一點題外話，最近發(fā)現(xiàn)了幾篇搬運我的文章到其他平臺的現(xiàn)象。每篇文章都是我精心打造的，都是自己的心肝寶貝，看到別人直接搬運過去也沒有標明作者和來源出處實在是太難受了。。為了最好的閱讀體驗，文中的圖片我都沒有加水印，但這也方便了他人搬運。今天考慮再三，還是不想違背自己的本意，畢竟我的讀者更為重要。

所以如果之后有小伙伴看到了，懇請大家后臺或者微信告訴我一下呀，非常感謝!

本文轉(zhuǎn)載自微信公眾號「 碼農(nóng)田小齊」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系 碼農(nóng)田小齊公眾號。