最小堆最大堆

最小堆、最大堆

最小堆（Min-Heap）和最大堆（Max-Heap） 是堆（Heap）数据结构的两种类型，它们都是完全二叉树，并且满足特定的堆性质。堆是一种优先级队列实现，通常用于高效地找出最值（最大或最小值）。堆的每个父节点都和其子节点满足一定的关系。

最小堆（又称：小根堆，小顶堆）
最大堆（又称：大根堆，大顶堆）

最小堆（Min-Heap）

最小堆1/ \2   3/ \   \5   6   4

• 定义：在最小堆中，父节点的值总是小于或等于其子节点的值。
• 性质：堆顶（根节点）的元素是整个堆中最小的元素。
• 结构：因为是完全二叉树，每次插入或删除时，堆结构会通过比较节点来维持堆性质。

插入和删除的规则：

1. 插入：将新元素放在堆的末尾，然后通过“向上调整”（上浮）来恢复堆的性质，即与父节点比较，如果新元素小于父节点，就交换位置，直到符合堆的性质。
2. 删除最小元素：将堆顶元素（最小值）移除，然后将最后一个元素移到堆顶，再通过“向下调整”（下沉）将其与子节点比较，直到恢复堆的性质。

最大堆（Max-Heap）

最大堆6/ \5   4/ \   \1   2   3

• 定义：在最大堆中，父节点的值总是大于或等于其子节点的值。
• 性质：堆顶（根节点）的元素是整个堆中最大的元素。
• 结构：同样是完全二叉树，插入和删除操作遵循与最小堆类似的方式，只是比较方向相反。

插入和删除的规则：

1. 插入：将新元素放在堆的末尾，然后通过“向上调整”（上浮）来恢复堆的性质，即与父节点比较，如果新元素大于父节点，就交换位置，直到符合堆的性质。
2. 删除最大元素：将堆顶元素（最大值）移除，然后将最后一个元素移到堆顶，再通过“向下调整”（下沉）将其与子节点比较，直到恢复堆的性质。

堆的主要操作及时间复杂度

• 插入元素：O(log n)，因为插入后可能需要调整堆的性质，最坏情况下需要从新元素的位置一直调整到根节点，最多经过堆的高度，即 log n 次比较和交换。
• 删除堆顶元素（最值）：O(log n)，删除堆顶元素后需要调整堆的性质，类似插入操作，最多需要 log n 次比较和交换。
• 获取堆顶元素（最值）：O(1)，堆顶元素始终是最小堆的最小值或最大堆的最大值，直接读取即可。

堆的常见应用

1. 优先队列：堆用于实现优先级队列，使得能够高效地获取优先级最高或最低的元素。
2. 排序算法：
   • 堆排序（Heap Sort）：通过构建最大堆或最小堆来实现排序，堆排序的时间复杂度为 O(n log n)，并且可以原地排序。
3. 寻找前 k 大或前 k 小元素：可以使用大小为 k 的最小堆（用于前 k 大）或最大堆（用于前 k 小）来高效寻找前 k 个特定元素。
4. 图算法：
   • Dijkstra 算法：用于单源最短路径算法，堆能够高效地维护未访问节点的最短路径。
   • Prim 算法：用于生成最小生成树，同样需要使用堆来维护当前可访问的最小边。

堆的数组表示

堆可以使用数组来实现，这是由于堆的完全二叉树结构具备的特性使得它可以映射到一个一维数组中。

节点索引规则

假设堆中某个节点位于数组的索引 i 处（i 是从 0 开始计数），那么：

• 父节点索引：节点 i 的父节点位于索引 (i - 1) / 2（向下取整）。
• 左子节点索引：节点 i 的左子节点位于索引 2 * i + 1。
• 右子节点索引：节点 i 的右子节点位于索引 2 * i + 2。

大根堆–堆排序

public static void heapSort(int[] arr) {if (arr == null || arr.length <= 1) return;// 构建大顶堆for (int i = (arr.length - 1) / 2; i >= 0; i--) {heapify(arr, i, arr.length);}// 堆排序int len = arr.length;while (len > 1) {// 理解成删除堆中一个元素  删堆顶元素 然后将最后一个元素放到堆顶 然后重新调整堆swap(arr, 0, len - 1); // 将堆顶元素与最后一个元素交换len--; // 因为数组后面的元素已经排序完成heapify(arr, 0, len); // 调整堆}
}// 调整堆
private static void heapify(int[] arr, int i, int len) {while (true) {int maxPos = i; // 假设当前节点是最大值int leftChild = 2 * i + 1;int rightChild = 2 * i + 2;if (leftChild < len && arr[leftChild] > arr[maxPos]) {maxPos = leftChild; // 如果左子节点大于当前节点 更新最大值位置}if (rightChild < len && arr[rightChild] > arr[maxPos]) {maxPos = rightChild;}if (maxPos == i) break;swap(arr, i, maxPos);i = maxPos;}
}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;
}

为什么从 (arr.length - 1) / 2 开始向上遍历？

假设堆中有 n 个元素，这些元素在数组中的索引是从 0 到 n-1。完全二叉树的特性决定了：

• 叶子节点不需要进行任何调整，因为它们没有子节点，不需要堆化。
• 只有非叶子节点需要进行 heapify 操作，即调整节点的位置，使其符合大顶堆的性质。

用数组表示的完全二叉树中：

• 叶子节点的索引：位于 n / 2 到 n-1 之间。
• 非叶子节点的索引：位于 0 到 (n/2 - 1) 之间。

为什么要进行 heapify？

heapify 是堆调整操作的核心，用来维护堆的性质。具体步骤如下：

• 假设节点 i 的子树已经是堆，但节点 i 本身可能不满足堆的性质（例如，节点 i 比其子节点中的某一个值要小）。
• 通过 heapify，我们将节点 i 与其子节点中较大的那个进行交换，然后递归地对交换后的位置继续进行调整，直到该子树成为一个合法的堆。

---

❤觉得有用的可以留个关注~❤