什么是堆？

简介

堆是一种高级数据结构，常用于排序和实现优先队列等应用场景。堆是具有两种特殊性质的完全二叉树。

堆必须是完全二叉树

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

完全二叉树的一些性质：

1. 所有叶子节点的深度要么为 $d$，要么为 $d-1$。
2. 深度为 $d$ 的叶子节点位于深度为 $d-1$ 的叶子节点的左侧。
3. 最多只有一个节点仅有一个子节点。
4. 如果存在唯一的单个子节点，则它必为其父节点的左子节点。
5. 如果存在唯一的单个子节点，则它是深度 $d$ 处最右侧的叶子节点。

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

堆序性质

节点必须满足堆序性质。本章将学习的两种堆结构对应的堆序性质有所不同：

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

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

最大堆性质：

在最大堆中，所有父节点的键值必须大于或等于其子节点的键值。因此，根节点始终保存堆中的最大元素。若节点 A 有一个子节点 B，则满足：

$key(A) >= key(B)$

最小堆性质：

在最小堆中，所有父节点的键值必须小于或等于其子节点的键值。因此，根节点始终保存堆中的最小元素。若节点 A 有一个子节点 B，则满足：

$key(A) <= key(B)$

堆的应用场景

堆的主要用途是快速获取最小或最大元素。由于从最小堆或最大堆中获取最小值或最大值的时间复杂度为 O(1)，即常数时间复杂度，因此可以优化那些频繁需要访问极值的算法。堆也常用于设计优先队列。一些著名的算法使用堆来实现，例如 Prim 算法、Dijkstra 算法，以及完全基于堆数据结构的著名堆排序算法。

堆在列表中的表示方法

堆可以通过 Python 中的数组或列表实现。节点值按特定方式存储：所有父节点位于列表的前半部分（索引满足 $index \leq floor(\frac{n-1}{2})$，其中 $n$ 是最后一个元素的索引），而叶子节点位于后半部分。因此，最后一个父节点位于 $floor(\frac{n-1}{2})$ 索引处。位于第 $k$ 个索引的节点，其左子节点位于 $2k+1$ 索引，右子节点位于 $2k+2$ 索引。换句话说，节点的索引相当于从根节点开始，按层从左到右依次编号（从 0 开始）。如下图所示，展示了节点如何映射到列表中：

[]

如图所示，所有父节点位于列表的前半部分，最后一个父节点出现在 $floor((n-1)/2)$ 位置。此处，“n”表示最后一个（即最大）索引，因此： $n = 9$ $floor((9-1)/2) = floor(8/2) = floor(4) = 4$

所以最后一个父节点位于索引 4，其键值为 50。子节点位于列表的后半部分。此外，以下两个关系式成立：

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

常见误解

堆有时被称为二叉堆，因为它们本质上就是二叉树。此外，堆数据结构与堆内存（heap memory）完全不同。还有一个普遍误解：认为堆中的元素是有序的。实际上，堆中的元素并不排序，堆唯一保证的条件是：根据堆的类型（最小堆或最大堆），最小或最大元素始终位于顶部（即根节点）。