最小(或最大)值永遠在頂端,看一眼 O(1)。用陣列存的完整二元樹,是優先佇列的引擎。
O(1),拿走後下一名自動補上。它是「優先佇列」的引擎,插入和取出都 O(log n)。
完整二元樹 —— 一層一層由左往右填滿,中間不留洞。
堆積性質 —— 每個父節點都 ≤ 它的孩子(最小堆);最大堆則相反。
頂端就是答案 —— 最小堆頂端永遠最小、最大堆頂端永遠最大,看一眼 O(1)。
兄弟不排序 —— 只管父子大小,左右兄弟誰大誰小不在乎。所以它不是 BST,找「任意值」要 O(n)。
堆積不用真的節點指標 —— 直接用一個陣列存,靠 index 算父子關係。
節點 i(從 0 起) —— 父 = (i-1)//2、左孩子 = 2i+1、右孩子 = 2i+2。
為什麼行得通 —— 因為是「完整二元樹」沒有洞,index 才能這樣精準對應到樹的位置。
好處 —— 省記憶體、又對 CPU 快取友善,這是堆積這麼實用的原因。下面的視覺化樹底下就附了陣列,對照著看。
push(插入) —— 放到陣列最後面,然後跟父節點比,比較小就往上換(sift-up 上浮),直到不再違反堆積性質。
pop(取出頂端) —— 把頂端答案拿走,將最後一個搬到頂端,再跟較小的孩子比、往下換(sift-down 下沉)。
都只走一條樹高的路 —— 樹高是 log n,所以 push、pop 都是 O(log n)。
O(log n);堆積只保證頂端,找任意值是 O(n)。要的是「一直拿最小 / 最大」就用堆積,要的是「有序又能查任意值」就用 BST。最危急的先處理,不管誰先到。處理完最急的,下一個最急的自動浮上來 —— 這就是優先佇列。
頂端永遠是目前第一名。把它拿走,下一名自動遞補上頂端。
永遠先挑最要緊的做,做完後最要緊的那件會自動浮到最上面。
一棵最小堆 [2, 5, 8, 9, 7, 12, 15]。插入新值時放到陣列最後,再一路跟父節點比:比父節點小就往上交換(上浮),直到不再違反。紫色是正在上浮的值、琥珀色是正在比較的父節點、綠色是定位完成。看樹和底下的陣列怎麼同步變。
用內建 heapq(最小堆)玩優先佇列、Top-K、堆積排序,再自己手刻一個 min-heap,並看資料流中位數、Dijkstra 等應用。
❌ 以為 heapq 是最大堆 —— 它是最小堆。要最大堆就把值取負丟進去,或用 key 取負。
❌ 想在堆積裡快速找 / 改任意值 —— 堆積只保證頂端,找任意值是 O(n)。要能快速查任意值請用別的結構。
❌ 「直接 sort 就好,何必堆積」 —— 若要「邊加新資料、邊不斷拿最小 / 最大」,堆積的 O(log n) 遠比每次重排的 O(n log n) 划算。
❌ 對空堆積 heappop —— 會 IndexError,先 if h: 檢查。
[2, 5, 8, 9, 7],index 3(值 9)的父節點是第幾格、值多少?index 1(值 5)的兩個孩子又是誰?[2, 5, 8, 9, 7, 12, 15] 插入 3,它會「上浮」到哪個 index?經過幾次交換?(用視覺化對答案)O(1),但「找某個特定值(例如 7)在不在」卻是 O(n)?堆積跟 BST 差在哪?把答案打到對話裡,我幫你對。