堆的基本概念与性质

简介

堆是一种高级数据结构，广泛应用于排序和优先队列的实现中。它们是具有两个特殊性质的二叉树：

• 堆必须是完全二叉树
• 节点必须满足堆序性质（Heap Order Property）

📝 堆 是一种二叉树，因此有时也被称为 二叉堆。

堆必须是完全二叉树

如在树章节中所述，完全二叉树是指除最后一层外，其余各层都被完全填满，且最后一层的节点从左到右依次排列的二叉树。

完全二叉树的一些特性：

1. 所有叶子节点位于深度 $d$ 或深度 $d-1$。
2. 深度为 $d$ 的叶子节点全部位于深度为 $d-1$ 的叶子节点左侧。
3. 最多只有一个节点只有一个子节点。
4. 如果存在只有一个子节点的情况，那么该子节点一定是其父节点的左子节点。

[第二棵树违反了第2、3、4条性质]

节点必须满足堆序性质

堆的构建基于堆序性质。在堆序性质中，我们比较父节点与子节点的关键值。根据本章将要学习的两种堆结构，堆序性质有所不同：

• 最小堆（Min Heap）
• 最大堆（Max Heap）

最小堆基于最小堆性质构建，最大堆基于最大堆性质构建。下面我们来具体看看它们的区别。

最大堆性质：

在最大堆中，所有父节点的关键值必须大于或等于其子节点的关键值。因此，根节点始终包含堆中的最大元素。如果节点 A 有一个子节点 B，则有：

$key(A) \geq key(B)$

最小堆性质：

在最小堆中，所有父节点的关键值必须小于或等于其子节点的关键值。因此，根节点始终包含堆中的最小元素。如果节点 A 有一个子节点 B，则有：

$key(A) \leq key(B)$

堆的应用场景

堆的主要用途是快速获取最小值或最大值。这是因为从最小堆或最大堆中获取最小/最大值的时间复杂度为 O(1)，即常数时间。这使得需要频繁查找最值的算法可以被高效优化。堆还被用于实现优先队列。一些著名的使用堆的算法包括 普里姆算法、迪杰斯特拉算法 以及著名的 堆排序算法，后者完全依赖于堆数据结构。

堆的表示方式

堆可以用 C++ 中的向量（vector）来实现。节点的值按层级从左到右依次存储在向量中，所有父节点位于向量的前半部分（索引满足 $index \leq \lfloor \frac{n-1}{2} \rfloor$，其中 $n$ 是最后一个索引），而叶子节点则位于后半部分。最后一个父节点位于 $\lfloor \frac{n-1}{2} \rfloor$ 的位置。

对于位于第 $k$ 个索引的节点：

• 左子节点位于 $2k+1$ 索引处
• 右子节点位于 $2k+2$ 索引处

简单来说，每个节点的索引就是从根节点开始（索引为0），按层级从左到右遍历整个树时所对应的计数位置。下图展示了节点如何映射到向量中：

（此处省略图像说明）

如图所示，所有父节点都位于向量的前半部分，最后一个父节点位于 $\lfloor \frac{n-1}{2} \rfloor$ 的位置。在此例中，$n = 9$，计算得：

$$\lfloor (9-1)/2 \rfloor = \lfloor 8/2 \rfloor = \lfloor 4 \rfloor = 4$$

因此最后一个父节点位于第 4 个索引，其键值为 50。子节点则出现在向量的后半部分。以下两个关系依然成立：

$$\text{左子节点} = 2k + 1$$ $$\text{右子节点} = 2k + 2$$

常见误解

堆数据结构与“堆内存”完全不同。此外，有人误以为堆中的元素是有序的。实际上，堆中的元素并非有序。堆唯一保证的条件是：根据堆的类型（最小堆或最大堆），最大值或最小值始终位于根节点（顶层）。