這是【字節(jié)可視化系列】堆排序的第一篇文章。同時，文末會放上一張【速記卡】，方便快速回顧本文關(guān)鍵知識點。
本篇的主旨是理解二叉堆結(jié)構(gòu)，所以具體實現(xiàn)代碼會留到第二篇講解。
提到堆，其實Java中的優(yōu)先隊列PriorityQueue就是基于堆結(jié)構(gòu)實現(xiàn)的；
而Java中的延遲隊列DelayQueue里面就用到了PriorityQueue；
再比如kafka中基于時間輪TimingWheel實現(xiàn)的延時定時器, 同樣離不開DelayQueue的配合。
這一切都和堆息息相關(guān)。
1 數(shù)組和樹
堆其實就是一個數(shù)組結(jié)構(gòu), 如圖
下面我們來點小魔法, 把數(shù)組變成樹!
這個數(shù)組對應(yīng)的樹結(jié)構(gòu)就是下面這樣:
數(shù)組結(jié)構(gòu)的下標(biāo)和樹結(jié)構(gòu)的節(jié)點對應(yīng)關(guān)系如下：
如果根節(jié)點對應(yīng)的數(shù)組下標(biāo)是0, 那么對于 i 節(jié)點，
左右子節(jié)點的位置為 2i +１和 2i+２；
i 節(jié)點的父節(jié)點位置為 ( i-1)/2；
簡單理解了數(shù)組和樹之后，下面我們進入正題。
2 最小堆結(jié)構(gòu)
首先我們來一個亂序的數(shù)組：
這個數(shù)組對應(yīng)的樹結(jié)構(gòu)：
這只是一個簡單的樹結(jié)構(gòu), 還不是堆, 堆結(jié)構(gòu)是下面這樣子的:
這是一個最小堆, 可以看到根節(jié)點, 也就是堆頂, 是數(shù)組中最小的那個元素。
同時，整一個大的堆, 是由很多個小的堆組成的。
比如左邊這個小堆, 也是符合最小堆的定義, 堆頂?shù)?是三個數(shù)字中最小的：
右邊的小堆也是一個最小堆, 堆頂?shù)?是最小的數(shù)字：
那么怎么把一顆樹變成一個最小二叉堆呢?
3 插入和上浮
最簡單的辦法, 就是新建一個空的堆(一個空的數(shù)組), 把亂序數(shù)組中的所有元素依次插入到堆中, 在這個過程中堆會通過上浮來調(diào)整自身的結(jié)構(gòu)。
下面我們來解析下上面的動畫:
首先, 是往堆中?插入?元素, 比如往下面的這個最小堆中插入數(shù)字1:
當(dāng)1插入數(shù)組尾部之后, 就處于樹的最后一個葉子節(jié)點的位置:
然后通過?上浮?操作, 把A移到合適的位置。
簡單來說就是先和A的父節(jié)點比較, 如果比父節(jié)點小, 就和父節(jié)點交換位置, 這個過程一直持續(xù)到A的父節(jié)點比A小, 或者A已經(jīng)到達堆頂?shù)奈恢谩?/p>
下面繼續(xù)數(shù)字1這個例子, 當(dāng)1插入數(shù)組尾部之后, 會和他的父節(jié)點8作比較:
1比父節(jié)點8小, 交換位置:
1再和他的父節(jié)點4作比較:
1比父節(jié)點4小, 交換位置后1到達堆頂, 形成了一個最小堆結(jié)構(gòu)。
4 刪除和下沉
接下來講講堆節(jié)點的刪除, 這里的刪除是指取出堆頂?shù)墓?jié)點。
我們把堆頂?shù)脑厝〕龊? 堆會把剩下的數(shù)字中最小的那個數(shù)字再次推到堆頂?shù)奈恢谩?/p>
仔細看動畫，這里值得注意的是, 取出堆頂?shù)脑? 并不是直接把堆頂?shù)脑貏h除。什么意思呢?
在JavaScript中, 數(shù)組的pop操作就是把數(shù)組中最后一個元素刪除; 而Java中的堆棧Stack也有pop操作, 同樣是把最后一個元素移除。
而堆的?刪除?操作, 也是基于pop操作來實現(xiàn)。這樣做是為了維持完全二叉樹的結(jié)構(gòu)。
比如我們要把堆頂?shù)?刪除：
1. 先把根節(jié)點和最后一個節(jié)點交換位置, 也就是1和6交換位置；
此時堆頂不再是最小的數(shù)字，最小堆的特性被打破, 接下來我們要對堆頂?shù)脑剡M行?下沉?操作, 把樹結(jié)構(gòu)重新調(diào)整為堆結(jié)構(gòu)。
2. 先比較左右子節(jié)點大小，與最小節(jié)點交換位置 ;
3. 繼續(xù)步驟2;
繼續(xù)上面的例子，當(dāng)1節(jié)點移除后，此時會先對堆頂6的左右子節(jié)點進行大小比較， 找出比較小的那個子節(jié)點，也就是右節(jié)點3：
然后， 節(jié)點6再和右節(jié)點3比較：
節(jié)點6下沉, 此時6已經(jīng)是葉子節(jié)點了, 下沉操作結(jié)束, 可以看到此時整棵樹已經(jīng)重新變回了最小堆結(jié)構(gòu)：
5 堆排序
有趣的是, 通過上面簡單的【插入并上浮】 和 【刪除并下沉】 , 我們就可以對亂序數(shù)組執(zhí)行堆排序了。
下面對亂序數(shù)組進行堆排序：
堆化，插入并上浮：
刪除并下沉：
排序完成后的數(shù)組：
最后對堆排序的總結(jié)就是:
1. 先把亂序數(shù)組堆化 (文中使用的是插入+上浮)
2. 再通過pop操作刪除堆頂元素, 通過下沉調(diào)整堆結(jié)構(gòu)
6 堆化 Heapify
平常的使用堆排序肯定不會再新建一個空的堆, 再把亂序數(shù)組的元素逐個插入堆中, 這樣太浪費空間, 下一章我們來講一下堆化。
7 色譜圖
簡單了解了堆排序后, 我們來看看16個元素進行堆排序后生成的色譜圖
也有網(wǎng)友說這是大腸圖, 感興趣的可以看看這篇文章了解下【譯】排序算法可視化之色譜圖， 后面本公眾號會開一個系列專門講解這種有趣的靜態(tài)可視化方法。
我們把這個圖拆成兩部分來看, 首先是左邊部分
這就是堆排序的第一步, 堆亂序數(shù)組堆化的過程
再來看看右邊部分
可以看到, 堆排序的第二步就是pop操作把堆頂元素移除, 圖中也體現(xiàn)得非常清晰,先把堆頂元素移到尾部, 被移除的元素就相當(dāng)于排好序了.
每次移除元素后, 都會對新的堆頂節(jié)點執(zhí)行下沉操作, 也就是圖中pop和pop之間的紅框部分, 我們可以清晰地看到堆在自我調(diào)節(jié)的過程
排序結(jié)束之后, 由淺到深的顏色依次呈現(xiàn)在我們眼前!
溫馨提示
文中的動畫是基于d3.js制作而成。
