計算機程序思維邏輯 (45)：深度解析堆數據結構與算法實現

計算機程序思維邏輯 (45)：深度解析堆數據結構與算法實現

在 Java 容器家族中，ArrayList 底層是動態數組，LinkedList 是鏈表，HashMap/HashSet 採用哈希表，TreeMap/TreeSet 基於紅黑樹。本文將介紹另一種高效的數據結構——堆，它是 PriorityQueue（優先級隊列）的核心實現，能優雅解決 Top-K、中位數、任務調度等經典問題。

什麼是堆？

注意區分兩個概念：

• 內存堆：JVM 運行時數據區，存放對象實例。
• 數據結構堆：邏輯上是完全二叉樹，物理上用數組存儲，且滿足父子節點順序關係。

完全二叉樹與數組映射

完全二叉樹：除最後一層外每層節點皆滿，最後一層節點靠左連續分佈。對節點按層序編號（從 1 開始），任意節點 i 的父節點為 i/2，左孩子 2i，右孩子 2i+1。此特性使樹可無縫映射到數組，索引即編號，父子關係隱含於索引運算中，省去指針開銷，空間緊湊、訪問極快。

最大堆與最小堆

• 最大堆：每個節點值 ≤ 父節點值，根節點為全局最大值。
• 最小堆：每個節點值 ≥ 父節點值，根節點為全局最小值。

堆允許重複元素，不要求完全有序，僅保證父子間的偏序關係。

核心操作與算法複雜度

以最小堆為例：

1. 插入元素 —— SiftUp（上浮）

新元素放入數組尾部，若小於父節點則交換，重複直到滿足堆性質或到達根。最多比較交換 log₂N 次，時間複雜度 O(log N)。

2. 刪除堆頂 —— SiftDown（下沉）

用最後一個元素覆蓋根，再與較小的孩子交換，重複直到滿足堆性質。同樣 O(log N)。

3. 刪除任意節點

用最後元素替代目標節點，視大小關係決定 SiftUp 或 SiftDown。

4. 建堆 —— Heapify（自底向上）

從最後一個非葉節點（索引 size/2）向前遍歷到根，對每個節點執行 SiftDown。驚人地是，建堆時間複雜度為 O(N)，而非 O(N log N)。

5. 查找與遍歷

堆無特殊查找結構，只能線性掃描數組，O(N)。遍歷即數組遍歷，順序無意義；但若反覆刪除堆頂，可得有序序列（堆排序）。

堆解決的三大經典問題

1. 優先級隊列：Java PriorityQueue 即基於最小堆，支持 O(log N) 入隊、出隊，適用於任務調度、Dijkstra 算法等。
2. Top-K 問題：維護大小為 K 的最小堆（求最大 K 個）或最大堆（求最小 K 個），單次處理 O(log K)，總體 O(N log K)，極適合海量數據流場景。
3. 動態中位數：雙堆法——大頂堆存小半部，小頂堆存大半部，堆頂即中位數，插入 O(log N)，查詢 O(1)。

總結

堆以「樹的邏輯、數組的存儲、偏序的性質」實現了高效的動態極值維護。理解 SiftUp/SiftDown 與 Heapify 是掌握堆的鑰匙。下一節將深入 PriorityQueue 源碼，並以代碼實戰 Top-K 與中位數問題。