堆

〇、返回

返回传送门

一、堆的定义

完全二叉树

堆是一种完全二叉树，这意味着：

除最后一层外，每一层都被完全填充，即从根节点开始，每层的节点数都达到最大值。

最后一层的节点尽可能靠左：如果最后一层没有被完全填充，那么所有的节点都集中在该层的最左边。

这种结构保证了堆可以在数组中高效地存储和访问。

堆序性

堆具有堆序性，这是堆的核心性质：

最大堆（大根堆）

对于堆中的每个节点，其值大于或等于其子节点的值。

最小堆（小根堆）

对于堆中的每个节点，其值小于或等于其子节点的值。

根节点（堆顶）是最大堆中的最大元素或最小堆中的最小元素。

二、堆的存储

堆通常使用数组来存储，这样可以方便地通过索引来访问节点及其子节点：

节点i的左子节点索引为2i（假设索引从1开始）。

节点i的右子节点索引为2i+1。

节点i的父节点索引为i/2向下取整。

这种存储方式使得堆的操作非常高效，因为可以直接通过简单的数学运算找到任意节点的父节点或子节点。

三、堆的基本操作

1. 插入元素

插入元素的过程如下：

(1) 将新元素添加到堆的末尾，这保持了完全二叉树的性质。

(2) 从该位置开始向上调整（Heapify Up）：

比较新元素与其父节点的值。

如果新元素的值大于（最大堆）或小于（最小堆）其父节点的值，则交换它们的位置。

继续这个过程，直到新元素满足堆的性质（即不大于其父节点的值）。

2. 删除元素（通常删除根节点）

删除元素（通常是根节点）的过程如下：

(1) 将根节点与堆的最后一个元素交换，这一步是为了移除根节点。

(2) 移除堆的最后一个元素，此时，原来的根节点已经被移除。

(3) 从新的根节点开始向下调整（Heapify Down）：

比较新根节点与其子节点的值。

如果新根节点的值小于（最大堆）或大于（最小堆）其子节点的值，则将其与较大的（最大堆）或较小的（最小堆）子节点交换。

继续这个过程，直到新根节点满足堆的性质（即不小于其子节点的值）。

3. 建堆

建堆有两种常见方法

(1) 逐个插入法：

从空堆开始，逐个插入元素。

每次插入后进行向上调整（Heapify Up）以维护堆的性质。

(2) 自底向上法（更高效）：

将所有元素放入数组中。

从最后一个非叶子节点开始，逐个进行向下调整（Heapify Down）以维护堆的性质。

这种方法的时间复杂度为O(n)，比逐个插入O(n log n)更高效。

四、堆的应用

1. 优先队列

堆是实现优先队列的一种高效数据结构。优先队列支持以下操作：

插入元素

将一个新元素添加到队列中。

删除最高优先级元素

移除并返回队列中优先级最高的元素（最大堆中的最大元素或最小堆中的最小元素）。

优先队列在许多算法中都有应用，例如：

Dijkstra 算法，用于寻找图中的最短路径。

Prim 算法，用于寻找图的最小生成树。

2. 堆排序

堆排序是一种基于堆的数据排序算法，其基本思想如下：

(1) 建堆

将待排序的数组构建成一个最大堆（升序排序）或最小堆（降序排序）。

(2) 逐个移除堆顶元素

将堆顶元素（最大或最小元素）与堆的最后一个元素交换。

移除堆的最后一个元素（即已排序的部分）。

对新的堆顶元素进行向下调整（Heapify Down）以维护堆的性质。

重复上述步骤，直到堆为空，此时数组即为排序后的结果。

堆排序的时间复杂度为O(n log n)，且不需要额外的存储空间，但是堆排序是不稳定的。

3. 查找第 k 大（小）元素

利用堆可以高效地找到一组数据中的第 k 大（小）元素：

使用最小堆查找第 k 大元素：

构建一个大小为 k 的最小堆。

遍历数组中的每个元素：

如果元素大于堆顶元素，则将其替换堆顶元素，并进行向下调整（Heapify Down）。

最终，堆顶元素即为第 k 大元素。

使用最大堆查找第 k 小元素：

构建一个大小为 k 的最大堆。