從零開始學Python (24)\u200a—\u200a資料結構模組heapq：除了前幾名以外，在座的各位都是垃圾

Day 24 資料結構模組heapq：除了前幾名以外，在座的各位都是垃圾

註：本篇文章同步刊載於iT邦幫忙，為鐵人賽之系列文章。
https://ithelp.ithome.com.tw/articles/10247299

昨天的題目，請參見下面的解法：
https://ithelp.ithome.com.tw/articles/10213277

接下來我們要來談談一個也算是蠻重要的資料結構：
堆積(heap)，以及在Python中對應的模組heapq 。

什麼是heap呢?
Heap是一種特別的完全二元樹。
這時候讀者又會問了：
那什麼是完全二元樹？
簡單來說，就是一棵二元樹直到最後一層之前，
由左往右都是填滿節點的狀態，中途沒有空缺，
唯有最後一層的右側會缺節點而已。

那麼，heap是怎麼個特別法呢？
當取一棵完全二元樹中的任何一個節點，
對應父(母)節點的值永遠小於等於子節點的值 (就是越上面越小)，
我們就會將其稱為最小堆積(min heap) ；
反之，如果父(母)節點的值永遠大於等於子節點的值 ，
我們就會稱為最大堆積(max heap) 。
如果上面兩個狀況都不符合的話就不是堆積囉！

也因此我們會得到一個特性：
最大堆積的最大的節點値 永遠會在根節點 ；
最小堆積的最小的節點値 永遠會在根節點 。

Python中的heapq的部分呢？
它是使用串列來實作出heap的資料結構的，
且是一個最小堆積 。
由於本篇以初學為導向，我們就不討論heap在二元樹上，
怎麼去處理新增/修改/刪除等操作了，
把焦點著重擺在heapq提供的可行操作上！

首先，Python可以將list輸入給heapq來排成heap的形狀，
透過heapq.heapify()函式 ：

1
2
3
4
5
6
7
>>> import heapq
>>> lt = [2,7,4,1,8,1]
>>> heapq.heapify(lt) # 直接將lt排成heap的形狀
# 在這個狀態下heap[k] <= heap[2*k+1] 且 heap[k] <= heap[2*k+2]
# 上面的k對於0或正整數均滿足(只要index存在)
>>> lt # 已經完成了，但並不是排序，所以看起來不會由小到大是正常的
[1, 1, 2, 7, 8, 4]

此外，由於現在lt已經是一個heap了，
要插入新的值或要處理其他操作的話，
要使用heapq提供的函式來處理，
常用的操作如下：
heapify (將一個list轉為heap)
heappush/heappop/heappushpop (放入/取出/先放入後取出)
nlargest/nsmallest (取前n大/前n小的元素)

當中我們只要只使用這些操作來處理，
就可以保證每次做取出(heappop)的時候，其値都會是最小的！
在這邊請留意幾點：

當使用append或者del (也就是用list的方式來動到lt)時，
會影響heap的狀態，若要復原只能重新heapify
由於這個heap是min heap，
所以nsmallest(取前n小元素)速度會比較快 ，較有效率，
nlargest(取前n大元素)是較沒有效率的，
官方會建議要這樣取不如直接先排序。
對於2來說，其實也有解法，
就是當需要用到max heap時，
我們手動將每個元素加上一個負號代入 ，
如此一來就可以將min heap當max heap來用啦！

我們拿LeetCode的1046題來當例子：
https://leetcode.com/problems/last-stone-weight/
題目大意是，
有一堆石頭，石頭重量均為正整數(阿不然是會有負的嗎？)。
每次我們拿最重的兩個石頭x, y(x <= y)相撞，
結果會有兩種：

x == y 的時候，兩顆石頭都會毀掉消失
x != y 的時候，只會剩下一顆石頭，重量為y — x
撞到最後，最多只會剩下1顆石頭，請問石頭的重量是多少？
(沒有石頭的話答案就視為0)

依照這個題目，我們會發現，
只要我們能建立一個max heap，
一切都會變得很輕鬆！
為什麼呢？
因為每次我們要拿兩個最重的相撞，
也就是每一輪要從heap當中取出兩個最大的值，
相減過後還有剩的，再放入heap中，
直到heap空掉，或者只剩1個值為止。

因此，我們可以如前面所提到的那樣，
先將石頭的重量加上負號並生成一個list，
再用heapq來對其處理。
我們直接來上程式碼，請對照註解來了解整個思路。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        import heapq
        h = [-x for x in stones] # list comprehension
        heapq.heapify(h) # 生成最小堆積
        while len(h) > 1: # 堆積內還有超過1顆的石頭
            y = heapq.heappop(h) # 取第一顆，重量應該是-y
            x = heapq.heappop(h) # 取第二顆，重量應該是-x
            if y != x: # 兩顆沒有一起毀掉
                # 差值應該是-y+x，但為了放入heap中，要再加上一個負號
                heapq.heappush(h, y - x) # 再放入heap中
        if len(h) == 0: # 全部石頭都毀掉了，回傳0
            return 0
        else:
            return -h[0] # 回傳剩下的石頭的值，別忘了要負負得正

除了上述的需求外，
heap類型也適用於限縮個數的狀況。
比如說今天想要找一個班級的最強的前5名，
我們可以讓heap在個數尚未達到5個時使用heappush() ；
而達到5個後呢？就使用heappushpop() ，
先放入值，再將最弱的取出來丟掉。
所以當碰到”除了前5名以外，在座的各位都是垃圾”類型 的情況，
特別適合使用heap來進行操作，可以有效降低需要保留的元素個數。

那麼，我們就明天見囉！

工商時間：

抽獎活動還在繼續累積人數(現在好像沒有人想抽XD)
在Python Taiwan的連結第100篇的文章 底下，
公開分享到你的臉書、按讚該篇文章、並留言告訴我說，
「你最喜歡這一整個系列的哪一篇？為什麼？」或
「除了從LeetCode學演算法系列以外，
你還想要看到關於什麼方向的文章？」
超過20則留言的話 (有完成以上步驟的才算)，我們就抽一組
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」
課程的免費兌換券進行贈送！

期限嘛…就延長到滿人數吧XDD (不然也沒辦法哈哈)

容筆者工商一下，
「從Leetcode學演算法｜進階篇」 開放預購啦！
這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈**「從Leetcode學演算法｜面試篇」** ！
當中包含了面試準備須知分享 ，及訪談國內外不同經驗的工程師 ，
讓你不論是想走前端/後端/一般軟工 或者是想找國外的工作 ，
是初學想轉職 還是正在工作 ，都能夠從中得到收穫呦！
有興趣的朋友可以使用下面的早鳥優惠～
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」 ：
https://bit.ly/advleetcode

「從Leetcode學演算法」全套(基礎/進階/面試篇)同捆優惠：
https://bit.ly/allleetcode