在计算机科学的诸多数据结构中，堆（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)。
