简介

简介

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

• 堆必须是完全二叉树。
• 节点必须满足堆序性质。

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

堆必须是完全二叉树

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

一些完全二叉树的特性如下：

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

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

应用堆序性质

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

• 最小堆
• 最大堆

最小堆基于最小堆性质构建，最大堆基于最大堆性质构建。它们之间的区别将在下一节详细说明。

最大堆性质

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

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

最小堆性质

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

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

堆的应用场景

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

[优先队列堆]

堆的表示方式

在 C# 中，堆可以用列表（数组）来实现。节点值的存储方式是：所有父节点位于向量的前半部分（其中 $index \leq floor(\frac{n-1}{2})$，$n$ 为最后一个索引），而叶子节点则位于后半部分。最后一个父节点位于 $floor(\frac{n-1}{2})$ 的索引位置。位于第 $k$ 个索引的节点，其左子节点位于 $2k+1$ 索引，右子节点位于 $2k+2$ 索引。简单来说，每个节点的索引值就是从根节点“0”开始，按层级从左到右遍历整个树时的计数值。下图展示了节点如何映射到向量中：

[堆在列表中的表示]

如图所示，所有父节点都位于向量的前半部分，最后一个父节点位于 $floor(\frac{n-1}{2})$ 的位置。在此例中，“n”为最大索引，即：

$n = 9$ $floor((9-1)/2) = floor(8/2) = floor(4) = 4$

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

$左子节点 = 2k+1$ $右子节点 = 2k+2$

常见误解

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