在計算機科學的諸多數據結構中，堆（Heap）無疑是最為重要和廣泛應用的一種。而在這其中，大根堆（Max-Heap）和小根堆（Min-Heap）更是其核心的兩種變體。它們以其獨特的性質，為高效解決各種演算法問題提供了強大的工具，例如優先順序隊列的實現、堆排序、Top K 問題以及動態中位數查找等。
本文將帶您深入剖析大根堆和小根堆的定義、性質、操作原理、核心區別以及它們在實際應用中的具體場景。無論您是初學者還是希望進一步鞏固理解的開發者，本文都將為您提供一個全面而詳盡的指南。
什麼是堆（Heap）？
在深入探討大根堆和小根堆之前，我們首先需要理解「堆」這一數據結構的基本概念。
堆的基本定義與性質
堆是一個特殊的完全二叉樹（Complete Binary Tree）。所謂完全二叉樹，是指除了最後一層外，其他層都是滿的，並且最後一層的節點都靠左排列。這一特性使得堆可以非常方便地用數組來表示，而不需要使用指針或鏈表，從而節省了存儲空間並提高了訪問效率。
除了完全二叉樹的結構特性外，堆還具有一個核心的堆序性（Heap Property）。正是這種堆序性，將堆進一步區分為大根堆和小根堆。
堆的數組表示法
由於堆是完全二叉樹，我們可以用一個一維數組來存儲所有節點，而無需顯式地存儲父子關係。
- 對於索引為
i的節點（數組下標從 0 開始）： - 其左子節點的索引是
2 * i + 1 - 其右子節點的索引是
2 * i + 2 - 其父節點的索引是
(i - 1) / 2（向下取整）
這種表示方法極大地簡化了堆的實現，並通過數組的隨機訪問特性，提高了操作效率。
大根堆（Max-Heap）詳解
大根堆，顧名思義，是一種特殊的堆，其核心特性在於「根」最大。
大根堆的定義與性質
一個大根堆（Max-Heap）滿足以下兩個主要條件：
- 它是一個完全二叉樹。
- 它滿足大根堆序性：任意一個父節點的值都大於或等於其所有子節點的值。
根據這些性質，我們可以得出結論：大根堆的根節點（即數組的第一個元素）一定是整個堆中最大的元素。
大根堆的核心操作
大根堆的常見操作包括插入元素、刪除最大元素和查找最大元素。
1. 插入元素（Insert）
當向大根堆中插入一個新元素時，為了保持堆的完全二叉樹結構和堆序性，通常遵循以下步驟：
- 將新元素添加到堆的末尾（即數組的下一個可用位置），以維持完全二叉樹的結構。
- 執行「上浮」（Swim / Heapify Up）操作：將新插入的元素與其父節點進行比較。如果新元素大於父節點，則交換它們的位置。重複此過程，直到新元素不大於其父節點，或者到達堆的根部。
上浮操作確保了新元素在不破壞大根堆序性的前提下，找到其正確的「位置」。
示例： 假設我們有一個大根堆[10, 8, 9, 5, 7]，現在插入元素12。
1. 將12添加到末尾：[10, 8, 9, 5, 7, 12]
2.12>9(父節點)，交換：[10, 8, 12, 5, 7, 9]
3.12>10(新父節點)，交換：[12, 8, 10, 5, 7, 9]
堆序性恢復，操作完成。
2. 刪除最大元素（Delete Max）
刪除大根堆中的最大元素（即根節點）是另一個常見操作。
- 將堆的根節點（最大元素）與堆的最後一個元素進行交換。
- 刪除交換后的最後一個元素（原根節點），堆的大小減一。
- 執行「下沉」（Sink / Heapify Down）操作：將新的根節點與其子節點進行比較。如果新的根節點小於其任一子節點，則與兩個子節點中較大的那個進行交換。重複此過程，直到新根節點不小於其子節點，或者到達堆的葉子節點。
下沉操作確保了在刪除最大元素后，剩餘元素仍能維持大根堆序性。
示例： 假設大根堆[12, 8, 10, 5, 7, 9]，刪除最大元素12。
1.12與9交換：[9, 8, 10, 5, 7, 12]
2. 刪除12：[9, 8, 10, 5, 7]
3.9<10(右子節點更大)，9與10交換：[10, 8, 9, 5, 7]
4.9(新位置) >5,7(子節點)，無需交換。
堆序性恢復，操作完成。
3. 查找最大元素（Peek Max）
這個操作非常簡單：直接返回堆的根節點（即數組的第一個元素）。時間複雜度為 O(1)。
大根堆的時間複雜度
- 插入操作：
O(log N)，因為上浮操作最多遍歷堆的高度。 - 刪除最大元素：
O(log N)，因為下沉操作最多遍歷堆的高度。 - 查找最大元素：
O(1)。 - 建堆操作（將無序數組轉換為大根堆）：
O(N)，雖然單個下沉是O(log N)，但通過從下往上對所有非葉子節點進行下沉，可以達到線性時間複雜度。
小根堆（Min-Heap）詳解
與大根堆相對，小根堆的特性是「根」最小。
小根堆的定義與性質
一個小根堆（Min-Heap）滿足以下兩個主要條件：
- 它是一個完全二叉樹。
- 它滿足小根堆序性：任意一個父節點的值都小於或等於其所有子節點的值。
由此可知，小根堆的根節點（即數組的第一個元素）一定是整個堆中最小的元素。
小根堆的核心操作
小根堆的操作與大根堆的操作邏輯非常相似，只是比較的方向相反。
1. 插入元素（Insert）
將新元素添加到堆的末尾，然後執行「上浮」操作：將新插入的元素與其父節點進行比較。如果新元素小於父節點，則交換它們的位置。重複此過程，直到新元素不小於其父節點，或者到達堆的根部。
2. 刪除最小元素（Delete Min）
將堆的根節點（最小元素）與堆的最後一個元素進行交換，然後刪除交換后的最後一個元素。接著執行「下沉」操作：將新的根節點與其子節點進行比較。如果新的根節點大於其任一子節點，則與兩個子節點中較小的那個進行交換。重複此過程，直到新根節點不大於其子節點，或者到達堆的葉子節點。
3. 查找最小元素（Peek Min）
直接返回堆的根節點（即數組的第一個元素）。時間複雜度為 O(1)。
