這是堆疊與佇列文章結尾預告的資料結構系列第 2 篇。本篇主角是 Heap，但開始前先釐清一個誤解。
相關文章堆疊與佇列完整整理：Swift 沒有 Stack 型別的原因（直到 removeFirst 陷阱）可同時了解背景概念與延伸應用案例。
**資料結構 Heap 只和記憶體 Heap 同名，完全無關。**記憶體的 Heap 區域是動態配置空間，而本文的 Heap 是「用 O(1) 取出最小值（或最大值）的樹」。
記憶體配置區域的差異在堆疊 vs Heap另行說明。本文只聚焦資料結構 Heap 與 Priority Queue。
如果你期待的是堆疊 vs Heap 文章中的那個 Heap，這裡是完全不同的世界。
Heap 要解決的問題很明確。
「想先處理最緊急的項目，但為此把全部排序好太浪費。」
排序是過度處理
假設要建立一個優先取出最高優先權工作項目的佇列。每次排序陣列，插入都要 O(n log n)。
即使維持排序狀態並尋找插入位置，移動元素仍需 O(n)。
仔細想想，我們需要的不是整體排序。只要能立即知道現在最緊急的一項就夠了。
第二名是誰，等第一名取出後再知道也不遲。
Heap 恰好只保證這些。因此插入和刪除都能在 O(log n) 完成。
「承諾越少，速度越快」是資料結構設計的典型取捨。
Heap 規則：父節點小於子節點，就這樣
最小 Heap 是完整二元樹，而且只有一條規則。
所有父節點都小於或等於自己的子節點。
不在意兄弟節點誰大。左子樹也不必小於右子樹。
只要遵守父子關係即可。這種寬鬆性讓根節點永遠是整體最小值，但不保證更多。
插入（sift up）：加到樹的末端後，若小於父節點就交換並向上移動。只需移動樹高，為 O(log n)。
取出最小值（sift down）：移除根節點，把末端元素移到根，再與兩個子節點中較小者交換並下移。同樣是 O(log n)。
用陣列建立樹的魔法
Heap 實作優雅的地方就在這裡。完整二元樹會從左到右逐格填滿，因此不需指標即可依序放入陣列。（NIST Heap）。
索引: 0 1 2 3 4 5
值: [1, 3, 2, 7, 4, 5]只靠索引計算就能得出親子關係。
- 父節點：
(i - 1) / 2 - 左子節點：
2i + 1，右子節點：2i + 2
沒有節點物件、子節點指標或 Heap 記憶體配置。這等於保留陣列 vs 連結串列中提到的快取區域性優勢，只借用樹的邏輯結構。
用 Swift 畫出骨架如下。
struct MinHeap<Element: Comparable> {
private var elements: [Element] = []
var min: Element? { elements.first } // O(1)
mutating func insert(_ value: Element) { // O(log n)
elements.append(value)
siftUp(from: elements.count - 1)
}
mutating func removeMin() -> Element? { // O(log n)
guard !elements.isEmpty else { return nil }
elements.swapAt(0, elements.count - 1)
let min = elements.removeLast()
siftDown(from: 0)
return min
}
}siftUp/siftDown是上面說明的重複交換。
順帶一提，將既有陣列整體建立成 Heap 的 build-heap 並非逐一插入的 O(n log n)。從下半部開始 sift down，可在**O(n)**完成——這是面試常考的細節。
Heap 在實務中的定位
**優先佇列就是 Heap。**借用堆疊與佇列文章的說法，佇列按到達順序取出，優先佇列按緊急程度取出，而 Heap 是它的標準實作（NIST Priority Queue）。
- OS 排程器：先將 CPU 分配給優先權較高的程序
- Dijkstra 最短路徑：反覆取出「目前找到的路徑中最短的一條」的演算法；沒有 Heap 效能會崩潰
- 計時器管理：系統內部只需知道大量計時器中最早響起的那個
- Heap Sort：全部放入再全部取出，即可完成 O(n log n) 排序。優點是無需額外記憶體即可原地排序
- Top-K 問題：「維持串流中最大的 K 個」——用大小為 K 的最小 Heap 可在 O(n log K) 解決，是常見的程式設計測驗模式
Swift 標準函式庫沒有 Heap。如同堆疊與佇列文章的 Deque，Apple 的swift-collections套件提供Heap（swift-collections Heap）。
這是能以 O(log n) 同時支援 min 與 max 的 min-max heap 實作。若像程式設計測驗一樣不能使用外部套件，熟悉上面的 MinHeap 骨架最實用。
總結
- 資料結構 Heap 和記憶體 Heap 只是名稱相同——它是「立即取出最小值的樹」
- 規則只有父節點 ≤ 子節點——放棄整體排序，換來插入與刪除 O(log n)
- 因為是完整二元樹，所以能不靠指標放在陣列中——父節點
(i-1)/2、子節點2i+1、2i+2 - 優先佇列的標準實作是 Heap，代表用途包括 Dijkstra、排程器與 Top-K
- Swift 使用 swift-collections 的
Heap，程式設計測驗則以自行實作為標準解法
下一篇是雜湊表。本文將探討 Swift Dictionary 如何實現 O(1)，以及 Hashable 要求的真正含義。
來源與驗證
- swift-collections HeapApple · 官方文件 · 查核 2026年8月17日依據: Swift Heap API 與最小／最大 Heap 的行為
- NIST Dictionary of Algorithms: Priority QueueNIST · 官方資料 · 查核 2026年8月17日依據: 優先佇列抽象資料型別的定義
- NIST Dictionary of Algorithms: HeapNIST · 官方資料 · 查核 2026年8月17日依據: 陣列式 Heap 的結構與操作特性