從零開始學Python (24) — 資料結構模組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()函式：
>>> 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來對其處理。 我們直接來上程式碼，請對照註解來了解整個思路。
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
請幫我隨手點開下面的SHOW EMBED並按5個like～ 喜歡的話也可以幫我拍拍手～ (按讚不用錢，感謝支持寫作~)
