CodeFarmer 技術週報 #7 - 淺談 Priority Queue 與 Heap
這週在練習 LeetCode 時遇到 Heap 與 Priority Queue 相關的問題，有感於對這個知識掌握度不夠高就趁這期來試著從頭複習一下
嗨嗨 👋 大家，歡迎閱讀第 7 期的 CodeFarmer 技術週報，這週在練習 LeetCode 時遇到 Heap 與 Priority Queue 相關的問題，有感於對這個知識掌握度不夠高就趁這期來試著從頭複習一下。
什麼是 Priority Queue？
如果舉個比較生活中的例子，假設今天許多人跑去大阪環球影城玩，所以熱門的 4D 哈利波特禁忌之旅設施大排長龍形成一個長長的隊伍 (Queue)。
爲了讓不同等級的消費者有不同的體驗，遊樂園就把遊客依照他的快速通關票的等級分成不同優先順序，付比較多錢的就能在設施有空閒時，被優先叫到號碼進去體驗，這種能從隊伍中快速找到優先值的概念就稱為 Priority queue (以下簡稱 PQ)。
具體來說什麼是 PQ 呢，這裡參考 WilliamFiset 有一系列關於 PQ 與 Heap 的影片 (連結) 來做筆記，借用圖來說明下：
參考上圖今天我們有一系列的操作想要從小到大在一個資料池中拉取資料，每次執行 poll 時就取出當前最小值，add 時就將資料加進去。在最後所有 poll rest 都完成後，會得到一個如下圖中的序列資料。
雖然以這個例子來說最後結果剛好是個從小到大的陣列，但其實只是操作上的巧合，會隨著 add 操作的順序不同而可能是非排序的結果。
而這個結構有什麼特別的呢？如果用人眼去看，每次想取出最小值時，可以直接從圖上很快找到是誰並取出，但要用什麼樣的資料結構可以讓程式更方便地去取出最小值呢？
這就要談到所謂的 Heap 了。
Heap (堆積)
Heap 在繁中翻作「堆積」、簡中翻作「堆」，而另一個很像的翻譯 stack 繁中翻作「堆疊」、簡中翻作「棧」，我自己覺得硬翻看起來會蠻混淆，就維持英文就好，只是先有個印象知道有些文章提到的「min heap (最小堆)」、「monotonic stack (單調棧)」的對應英文是什麼就好。
講回正題，什麼是 Heap 呢？
廣義來說，Heap 是一種特殊的樹狀資料結構，在某些問題中我們更關注資料中當前的最大值或最小值是誰，其他資料的取得效率相對較不在乎時，就可以用 Heap 這樣的結構來實現。
舉例 Heap 可以像是這些樣貌，以下兩個都被稱為 min heap，也就是每個節點的值都小於或等於其底下的子節點們的值：
Binary heap
而其中在實現 PQ 時，比較常見的做法就是使用 Binary heap 來實作，也就是每個節點下只會有兩個子節點，並具有以下特性：
是一種特殊的 binary tree
需為 complete binary tree (子節點需從左至右填滿)
每個節點的值必須 ≥ 或 ≤ 其子節點值
特性
插入與刪除元素的時間複雜度都是 O(logN)
可用 O(1) 的時間複雜度取得堆中的最大值或最小值
分類
Min Heap
Max Heap
PQ 不等於 Heap
有一個常見的需要釐清的誤解是 PQ 不等於 Heap。
技術上我們會說 Priority queue 是一種抽象資料型別 (ADT)，也就是一種拿來解決優先順序問題的概念，他的實現方式可以是用各種資料結構來做：
Array、Linked list：僅保證插入、刪除時，其中一個操作的時間複雜度為 O(1)，另一個則為 O(N)
Heap：使用 Heap 這個資料結構來實作的話，就能保證插入、刪除都是 O(logN)
這也是為什麼有些 LeetCode 題目中，通常會提到一個 follow up question 是當今天插入、刪除的操作有可能有 10^n 時，是否有更有效率的做法？
實戰解題：3066. Minimum Operations to Exceed Threshold Value II
會開始理解 PQ 也是因為前幾天在 daily 中遇到這題 (題目連結)，題目寫得很長但其實要求很簡單，直接看上面的範例，想找到可以對 nums 陣列在進行最小次數的操作後，讓陣列中所有數都大於等於 k。
這個每次操作的定義是「移除 nums 中最小兩個數 x, y，並將 min(x, y) * 2 + max(x, y) 添加回 nums」。
這樣的題目如果是用一個陣列排序後不斷地取出、插入值、檢查大家是否都大於等於 k 相對會比較沒效率，但如果直接先將 nums 轉成 min heap 的結構就會容易許多。
關於詳細的解題筆記有興趣的讀者可以參考部落格好讀版 (連結)。
在稍微複習了下基礎 priority queue 與 heap 的概念後，才發現原來像是 Python 的 heapq、C++ 的 priority_queue、Java、Go 等這些語言都有內建 heap 的資料結構。
而如果使用 JavaScript/TypeScript 的話，很抱歉，這需要自己實作，甚至有個專門的套件 (@datastructures-js/heap、@datastructures-js/priority-queue) 能直接調用，也難怪大家為什麼這麼推薦用 Python 來寫 LeetCode 了嗎 😆
2025-03-15 補充：後來經過古古的友情提醒與研究，發現如果是使用 LeetCode 並搭配 JavaScript/TypeScript 進行 PQ 相關的解題時，預設平台是會自動載入上述兩個套件輔助更方便善用像是 min heap 或 max heap 的資料結構。而 Python 有另一個限制是原生並沒有提供 max heap，查了下資訊看起來會需要調整成負數形式來用 min heap 實作。
今天就先筆記到這，關於 PQ 與 Heap 還有一些可以再深入探討的地方，之後再來回頭繼續。
本期推薦內容
上週提到這個月開始在寫 daily，後來與一位佛心前輩 Yeng 大聊完後，他認為初期建議不要寫 daily，因為主題會太雜，除非是已經練熟 NeetCode 150，只是想保持手感，如果是為了面試需求不如把經典考題刷個 5 到 10 遍 CP 值更高，並要熟練到知道每個經典題有哪些解法、複雜度如何？每個解法的利弊如何？另外也可以參考在 Threads 上看到的 Lamber 大這篇心得的做法 (連結)，觀點上也差不多，而其中提到的 rating 的分級參考也比單純分 Medium、Hard 來得更精準一些。其中也有推薦一個非常強大的筆記集合 (連結)。
對於職涯上「該去新創、該去大公司、該去外商」這個週期性問題，後來看了 Yeng 大之前寫的《火箭新創與穩定外商，該怎麼選？》這篇文章後，覺得其中討論到的「問自己現在這個階段你需要的是什麼？」以及「市場上有哪些機會？」這些觀點蠻不錯的。(連結)
在系統設計面試準備上，也推薦可以參考 HelloInterview 的免費教材 (連結)，比起 ByteByteGo 相關資源，算是可以漸進式增強且能及時派上用場的版本。
最近看了 Jacky 的電扶梯走左邊中訪問 Google NotebookLM 工程師胡程維的影片 (連結)，其中有提到在職涯中有時覺得雖然環境不是自己完全喜歡的，但能在其中遇到厲害的人才是他更重視的，對此 Jacky 也給了一句註解：「It’s not about the destination nor the journey, it’s about the companionship.」。除此之外其中還有許多不錯的觀點推薦一看，看完也認為自己應該在今年找到幾本人生之書才是，在這個短文短影充斥的時代閱讀還是件很重要的事。
這幾天 xAI 的 Grok 3 新模型討論度很高，雖然對於 AI 新知快學不動了，也分享下 Tesla AI 總監 Andrej Karpathy 的實測優劣分析 (連結)。
關於瀏覽器，最近我終於忍痛離開不再維護的 Arc，過程中嘗試過 Safari，體感渲染效能較好，但可惜的是沒有擴充生態系。也試過 Theo 在最近的影片中提到他最後選擇的 Zen (連結)，但實際試用後覺得 firefox based 的生態系仍有一些擴充無法取得也是痛點，雖然以體驗上來說是比較接近 Arc 的。最後目前是回到最樸實無華的 Chrome，但有時比起其他 chromium 瀏覽器還是比較卡一點，暫時還是有點困擾，也好奇大家最近都用什麼瀏覽器，歡迎與我分享交流！
以上就是本期的 CodeFarmer 技術週報的所有內容了，若內容有什麼錯誤、問題、討論也都歡迎透過以下管道與我交流，或直接留言與回覆這封電子信我也能收到：
Email：codefarmer.tw@gmail.com
喜歡本期的內容也歡迎按讚，並分享給有興趣、正在努力學習路上的朋友一起來免費訂閱週報一同交流討論，那我們就下週三見了！