介绍大根堆小根堆

小根堆（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)查找极值）；
• 选择哪种堆，取决于场景需要“快速获取最小值”还是“快速获取最大值”，两者操作逻辑对称，仅比较方向不同。