小根堆（Min-Heap）和大根堆（Max-Heap）是完全二叉樹的兩種特殊形式，屬于“堆（Heap）”數據結構的核心類型，核心特性是“父節點與子節點的優先級關系固定”，主要用于高效獲取極值（最小值/最大值）和實現排序、優先隊列等場景。

一、核心定義與結構特性

堆的本質是“完全二叉樹”（除最后一層外，每一層節點數均滿；最后一層節點從左到右連續排列，不允許中間空缺），其核心規則由“根堆類型”決定：

類型	核心規則（父子節點關系）	關鍵特征
小根堆（Min-Heap）	任意父節點的值 ≤ 其左右子節點的值	整個堆的最小值一定在根節點
大根堆（Max-Heap）	任意父節點的值 ≥ 其左右子節點的值	整個堆的最大值一定在根節點

示例（以“數組存儲堆”為例）

堆通常用數組存儲（利用完全二叉樹的索引特性，無需額外存儲指針），若父節點索引為i（從0開始），則：

• 左子節點索引：2i + 1

• 右子節點索引：2i + 2

• 小根堆數組示例：[1, 3, 2, 8, 5, 4]（根為1，每個父節點≤子節點）

• 大根堆數組示例：[8, 5, 4, 3, 1, 2]（根為8，每個父節點≥子節點）

二、堆的兩個核心操作

堆的功能依賴“插入”和“刪除極值”兩個操作，操作后需通過“堆化（Heapify）”維持堆的規則，避免結構紊亂。

1. 插入操作（以小根堆為例）

1. 尾插：將新元素插入數組的最后一位（對應完全二叉樹的最后一個節點）；
2. 向上堆化（Sift Up）：比較新元素與父節點的值，若新元素更小（小根堆規則），則交換兩者；重復此過程，直到新元素≥父節點或成為根節點，堆規則恢復。

2. 刪除極值操作（以小根堆為例，刪除根節點的最小值）

1. 替換根：數組滿的情況下插入更優數據或需要取出根節點時，將數組最后一位元素移到根節點位置（覆蓋并刪除原根節點）；
2. 向下堆化（Sift Down）：比較根節點與左右子節點的最小值，若根節點更大，則與最小子節點交換；重復此過程，直到根節點≤子節點或成為葉子節點，堆規則恢復。

三、小根堆 vs 大根堆：對比與適用場景

兩者核心差異在于“極值位置”和“堆化時的比較邏輯”，適用場景隨需求（取最小/最大值）而定：

維度	小根堆（Min-Heap）	大根堆（Max-Heap）
極值位置	根節點（O(1)獲取最小值）	根節點（O(1)獲取最大值）
堆化比較邏輯	向上堆化：新元素＜父節點則交換	向上堆化：新元素＞父節點則交換
	向下堆化：父節點＞子節點最小值則交換	向下堆化：父節點＜子節點最大值則交換
核心適用場景	1. 快速獲取/刪除最小值（如優先隊列中“最小任務優先執行”）； 2. 海量數據中找Top K（如找最大的100個數，用小根堆維護候選集）； 3. 實現堆排序（升序排序）	1. 快速獲取/刪除最大值（如優先隊列中“最大任務優先執行”）； 2. 海量數據中找Top K（如找最小的100個數，用大根堆維護候選集）； 3. 實現堆排序（降序排序）
時間復雜度	插入、刪除極值均為 O(log n)（堆化過程最多遍歷樹的高度，完全二叉樹高度為log?n）	同小根堆，插入、刪除極值均為 O(log n)

四、典型應用場景

1. 優先隊列（Priority Queue）：

堆是優先隊列的底層實現，例如：

• 小根堆實現“最小優先隊列”（如操作系統中“短任務優先”調度）；
• 大根堆實現“最大優先隊列”（如電商平臺“高優先級訂單優先處理”）。

2. 堆排序：

• 用大根堆實現降序排序：反復取出根節點（最大值）放到數組末尾，再堆化剩余元素；
• 用小根堆實現升序排序：反復取出根節點（最小值）放到數組末尾，再堆化剩余元素。

3. Top K 問題：

• 找“最大的K個數”：用大小為K的小根堆，遍歷數據時，比堆頂大的元素替換堆頂并堆化，最終堆內即Top K；
• 找“最小的K個數”：用大小為K的大根堆，遍歷數據時，比堆頂小的元素替換堆頂并堆化，最終堆內即Top K。

代碼示例

/*** 使用java數組實現一個n=10的小根堆，實現包括插入和刪除根節點方法**/
public class MinHeap {private int[] heap;  // 存儲堆的數組private int size;    // 當前堆的大小private int capacity; // 堆的最大容量// 構造函數，初始化容量為10的小根堆public MinHeap() {this.capacity = 10;this.heap = new int[capacity];this.size = 0;}// 獲取父節點索引private int parent(int i) {return (i - 1) / 2;}// 獲取左子節點索引private int leftChild(int i) {return 2 * i + 1;}// 獲取右子節點索引private int rightChild(int i) {return 2 * i + 2;}// 交換兩個索引位置的元素private void swap(int i, int j) {int temp = heap[i];heap[i] = heap[j];heap[j] = temp;}// 插入元素到堆中public void insert(int value) {if (size == capacity) {System.out.println("堆已滿，無法插入新元素");return;}// 先將新元素插入到最后位置size++;int i = size - 1;heap[i] = value;// 向上堆化：如果新元素小于其父節點，則交換它們while (i != 0 && heap[parent(i)] > heap[i]) {swap(i, parent(i));i = parent(i);}}// 向下堆化：當根節點被刪除后，重新維護堆的性質private void heapify(int i) {int left = leftChild(i);int right = rightChild(i);int smallest = i;// 找到當前節點、左子節點、右子節點中的最小值if (left < size && heap[left] < heap[smallest]) {smallest = left;}if (right < size && heap[right] < heap[smallest]) {smallest = right;}// 如果最小值不是當前節點，則交換并繼續向下堆化if (smallest != i) {swap(i, smallest);heapify(smallest);}}// 刪除并返回根節點（最小值）public int deleteRoot() {if (size <= 0) {throw new IllegalStateException("堆為空，無法刪除元素");}if (size == 1) {size--;return heap[0];}// 保存根節點的值int root = heap[0];// 將最后一個元素移到根節點位置，并減小堆大小heap[0] = heap[size - 1];size--;// 從根節點開始向下堆化heapify(0);return root;}// 打印堆中的元素public void printHeap() {System.out.print("小根堆元素: ");for (int i = 0; i < size; i++) {System.out.print(heap[i] + " ");}System.out.println();}// 測試小根堆的實現public static void main(String[] args) {MinHeap minHeap = new MinHeap();// 插入元素minHeap.insert(5);minHeap.insert(3);minHeap.insert(8);minHeap.insert(1);minHeap.insert(6);minHeap.insert(2);minHeap.printHeap(); // 應該輸出: 1 3 2 5 6 8// 刪除根節點（最小值）System.out.println("刪除的根節點值: " + minHeap.deleteRoot()); // 應該輸出: 1minHeap.printHeap(); // 應該輸出: 2 3 8 5 6// 繼續插入元素直到堆滿minHeap.insert(4);minHeap.insert(7);minHeap.insert(9);minHeap.insert(0);minHeap.insert(10);minHeap.printHeap(); // 應該輸出: 0 2 8 3 6 10 4 5 7 9// 嘗試插入第11個元素（堆已滿）minHeap.insert(11); // 應該提示堆已滿}
}

總結

• 小根堆和大根堆是“完全二叉樹+固定父子優先級”的結合，核心價值是O(1)獲取極值、O(log n)插入/刪除，效率遠高于數組（O(n)查找極值）；
• 選擇哪種堆，取決于場景需要“快速獲取最小值”還是“快速獲取最大值”，兩者操作邏輯對稱，僅比較方向不同。