堆的定义与性质

简介

堆是一种高级数据结构，适用于需要排序或实现优先队列的场景。它们是具有两个特殊性质的普通二叉树。

堆必须是完全二叉树

完全二叉树是指每个节点最多有两个子节点，并且除最后一层外，所有层的节点都已填满，而最后一层的节点可以为空。

一些完全二叉树的特性：

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

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

节点必须满足堆序性质

堆序性质在以下两种堆结构中有所不同：

• 最小堆
• 最大堆

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

最大堆性质：

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

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

最小堆性质：

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

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

堆的应用场景

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

堆在数组中的表示

堆可以用数组在 JavaScript 中实现。

节点的值按顺序存储，使得所有父节点位于数组的前半部分（其中 $index \leq floor(\frac{n-1}{2})$，$n$ 为最后一个索引），而叶子节点则位于后半部分。因此，最后一个父节点位于 $floor(\frac{n-1}{2})$ 的索引位置。第 $k$ 个索引处节点的左子节点位于 $2k+1$ 索引处，右子节点位于 $2k+2$ 索引处。

简单来说，每个节点的索引值相当于从根节点开始（索引为0）按层级从左到右遍历整棵树时的计数位置。下图展示了节点如何映射到数组中：

[]

如图所示，所有父节点都位于数组的前半部分，最后一个父节点位于 $floor(\frac{n}{2})$ 的位置。此处 $n$ 是最大索引，即
$n = 9$
$floor(\frac{9-1}{2}) = floor(\frac{8}{2}) = floor(4) = 4$

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

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

常见误解

堆有时被称为 二叉堆，因为它们是二叉树。此外，堆数据结构与堆内存并不是同一个概念。

另外，人们常常误以为堆中的元素是有序的。实际上，堆中的元素并不排序。

实际上，堆唯一遵循的条件是：根据堆的类型（最小堆或最大堆），最大值或最小值始终位于顶部（根节点）。