Java集合中堆的打開方式是什么

本篇內(nèi)容主要講解“Java集合中堆的打開方式是什么”，感興趣的朋友不妨來看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“Java集合中堆的打開方式是什么”吧!

什么是堆?

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

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

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

還有其實(shí)每個(gè)人回復(fù)微信消息也是默默的把消息放進(jìn)堆里排個(gè)序：先回男朋友女朋友的，然后再回其他人的。

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

我們?cè)賮砘仡櫼幌隆付选乖谡麄€(gè) Java 集合框架中的位置：

也就是說，

• PriorityQueue 是一個(gè)類 (class);

• PriorityQueue 繼承自 Queue 這個(gè)接口 (Interface);

那 heap 在哪呢?

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

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

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

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

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

這個(gè)數(shù)組的排列方式有點(diǎn)特別，因?yàn)樗倳?huì)維護(hù)你定義的(或者默認(rèn)的)優(yōu)先級(jí)最高的元素在數(shù)組的首位，所以不是隨便一個(gè)數(shù)組都叫「堆」，實(shí)際上，它在你心里，應(yīng)該是一棵「完全二叉樹」。

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

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

這個(gè)就涉及完全二叉樹的性質(zhì)了，我們下一篇會(huì)細(xì)講，簡(jiǎn)單來說，因?yàn)橥耆鏄涞亩x要求了它在層序遍歷的時(shí)候沒有氣泡，也就是連續(xù)存儲(chǔ)的，所以可以用數(shù)組來存放;第二個(gè)問題當(dāng)然是否。

堆的特點(diǎn)

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

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

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

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

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

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

比如對(duì)于節(jié)點(diǎn) 3 來說，

• 它的 Index = 1，

• 它的 parent index = 0,

• 左孩子 left child index = 3,

• 右孩子 right child index = 4.

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

• 設(shè)當(dāng)前節(jié)點(diǎn)的 index = x,

• 那么 parent index = (x-1)/2,

• 左孩子 left child index = 2*x + 1,

• 右孩子 right child index = 2*x + 2.

有些書上可能寫法稍有不同，是因?yàn)樗鼈兊臄?shù)組是從 1 開始的，而我這里數(shù)組的下標(biāo)是從 0 開始的，都是可以的。

這樣就可以從任意一個(gè)點(diǎn)，一步找到它的孫子、曾孫子，真的太方便了，在后文講具體操作時(shí)大家可以更深刻的體會(huì)到。

基本操作

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

這里 peek() 的時(shí)間復(fù)雜度很好理解，因?yàn)槎训挠猛揪褪悄軌蚩焖俚哪玫揭唤M數(shù)據(jù)里的最大/最小值，所以這一步的時(shí)間復(fù)雜度一定是 O(1)  的，這就是堆的意義所在。

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

offer(E e)

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

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

所以說，

• 我們先保證加了元素之后這棵樹還是一棵完全二叉樹，

• 然后再通過 swap 的方式進(jìn)行微調(diào)，來滿足堆序性。

這樣就保證滿足了堆的兩個(gè)特點(diǎn)，也就是保證了加入新元素之后它還是個(gè)堆。

那具體怎么做呢：

Step 1.

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

OK!總算先上岸了，然后我們?cè)僖徊讲酵献摺?/p>

這里「能否往上走」的標(biāo)準(zhǔn)在于：

是否滿足堆序性。

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

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

Step 2. 與 5 交換

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

Step 3. 與 3 交換

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

Step 4. 與 1 交換

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

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

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

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

時(shí)間復(fù)雜度

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

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

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

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

poll()

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

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

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

我們還是先來滿足堆序性，因?yàn)楸容^容易滿足嘛，直接從最后面拿一個(gè)來補(bǔ)上就好了，先放個(gè)傀儡上來。

Step1. 末尾元素上位

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

那 8 比 7 和 3 都大，應(yīng)該和誰(shuí)交換呢?

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

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

Step 2. 與 3 交換

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

Step 3. 與 4 交換

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

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

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

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

時(shí)間復(fù)雜度

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

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

heapify()

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

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

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

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

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

這個(gè) constructor 的時(shí)候，人家會(huì)自動(dòng)調(diào)用 heapify() 這個(gè)操作。

那具體是怎么做的呢?

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

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

因?yàn)槿~子節(jié)點(diǎn)沒必要操作嘛，已經(jīng)到了最下面了，還能和誰(shuí) swap?

舉個(gè)例子：

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

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

Step 1.

尷尬 ?，3 并不用交換，因?yàn)橐运鼮轫旤c(diǎn)的這棵小樹已經(jīng)滿足了堆序性。

Step 2.

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

交換完成后;

Step 3.

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

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

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

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

好了難點(diǎn)來了，為什么時(shí)間復(fù)雜度是 O(n) 的呢?

怎么計(jì)算這個(gè)時(shí)間復(fù)雜度呢?

其實(shí)我們?cè)谶@個(gè)過程里做的操作無非就是交換交換。

那到底交換了多少次呢?

沒錯(cuò)，交換了多少次，時(shí)間復(fù)雜度就是多少。

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

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

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

到此，相信大家對(duì)“Java集合中堆的打開方式是什么”有了更深的了解，不妨來實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！