二叉堆是一种采用完全二叉树形式组织的数据结构,其中每个父节点的键与其子节点的键之间都满足特定的顺序关系。在最小堆中,每个父节点的键都不大于其子节点的键;在最大堆中,则都不小于其子节点的键。因此,两者的根节点分别包含最小键或最大键。二叉堆通常存储在数组中,广泛用于实现优先队列和堆排序算法。
结构与顺序
二叉堆满足两个相互独立的条件:
- **形状性质:**除最底层可能未填满外,其余各层均填满,且最底层从左到右依次填充。
- **堆序性质:**在选定的优先级顺序下,每个父节点的优先级都高于或等于其子节点。
对于键函数为 的最小堆,顺序条件为
其中 为任意非根节点。最大堆则将不等号反向。堆中允许存在重复键。
形状性质保证了包含 个元素的非空堆,其高度为
这里的高度以边数计量。这一对数级高度限制了插入和移除操作需要经过的层数。
堆序只是元素之间的一种偏序关系。它约束祖先节点与后代节点之间的顺序,但通常不规定兄弟节点之间或不同子树中元素之间的顺序。例如,数组
[2, 5, 3, 9, 7, 8, 4]
虽然并未排序,却表示一个有效的最小堆。
因此,二叉堆不同于二叉搜索树。搜索树通过规定左右子树中键的顺序来支持查找;堆则让极值键可以直接访问,但并不维护足以高效查找任意键的顺序信息。
数组表示
二叉堆通常用数组(数据结构)表示,而不是使用分别分配、通过指针连接的节点。完全二叉树的结构使得节点间的关系可以直接由数组位置推导出来。
采用从零开始的索引时,索引为 的节点具有以下关系:
只有当子节点的索引小于当前堆大小 时,该子节点才存在。采用从一开始的索引时,对应的索引分别为 、 和 。
这种表示无需显式保存节点之间的链接,并按层序存储堆。它的单个元素额外开销较低,通常具有良好的空间局部性,不过在较大的堆中,从根到叶的路径仍可能跨越多个CPU 缓存行。
堆的逻辑大小必须与数组容量区分开来。超出逻辑大小的数组槽位不属于堆。
基本操作
以下描述以最小堆为例。最大堆的操作只需将比较方向反转。
查看最小值
最小值存储在根节点,因此查看它需要 时间。对于空堆,除非接口规定了错误、哨兵值或可选结果,否则该操作没有定义。
插入与上浮
插入时,首先将元素追加到下一个可用位置,以保持完全二叉树的形状。随后将该元素与其父节点比较。如果它的键更小,就与父节点交换,并继续向上进行这一过程。
这一操作称为上浮(sift-up、bubble-up 或 percolate-up)。只有新元素到根的祖先路径可能违反堆序,因此修复这条路径即可恢复不变式。
在最坏情况下,插入所需的堆调整工作为 。如果底层数组需要扩容,单次插入还可能需要 的复制或移动操作。若容量按几何倍数增长,数组扩容带来的开销摊还到每次插入为 。
移除最小值与下沉
移除根节点的步骤如下:
- 保存根元素。
- 将最后一个元素移到根位置,并减小堆大小。
- 将替换上来的元素与其子节点比较。
- 如果它大于较小的那个子节点,就交换两者,并继续向下进行这一过程。
这一修复操作称为下沉(sift-down、bubble-down 或 percolate-down)。选择较小的子节点至关重要:如果将较大的子节点上移,它可能仍大于其兄弟节点。
移除操作在最坏情况下需要 时间。只有一个元素的堆在移除后直接变为空堆。
以下伪代码在从零开始索引的最小堆中执行下沉操作,假设各子树已经满足堆序:
sift_down(A, i, n):
while 2*i + 1 < n:
child = 2*i + 1
right = child + 1
if right < n and A[right] < A[child]:
child = right
if A[i] <= A[child]:
break
swap A[i], A[child]
i = child
实现时可以借助一个临时“空位”移动元素,而不必反复交换,从而减少赋值次数,同时保持相同的渐近界。
修改优先级与删除已知位置的元素
如果已知元素的位置,在最小堆中减小它的键可能需要上浮,增大它的键则可能需要下沉。两种操作都需要 时间。
对于位置已知的任意元素,可以用最后一个元素替换它,再视情况向上或向下修复,从而完成删除。这同样需要 时间。
“位置已知”这一前提十分重要。在普通二叉堆中查找特定值,最坏情况下需要 时间。索引优先队列会额外维护从元素标识符到堆中位置的映射,通常使用数组或哈希表实现。堆中每次移动元素时,都必须更新这一映射。
建堆
可以通过反复插入元素来构建堆,最坏情况下需要 时间。更高效的方法是自底向上构建。
对于长度为 、从零开始索引的数组,从 开始的所有位置都是叶节点,各自已经满足堆序。算法从最后一个内部节点 开始,按索引递减的顺序对每个位置执行下沉,直至根节点。
这一过程通常称为自底向上建堆或 build-heap,需要 时间。它通常与罗伯特·W. 弗洛伊德关于堆排序的工作联系在一起。
线性时间界源于大多数节点都靠近叶节点,只能移动很短的距离。总工作量的一个上界正比于
虽然一次下沉可能花费 时间,但只有很少一部分节点具有这么大的可下沉高度。因此,将下沉的最大开销乘以节点总数,只能得到一个较宽松的上界。
heapify 一词存在歧义:有些接口用它表示构建整个堆,而有些算法说明则用它表示一次下沉操作。
复杂度
在键比较和元素移动均耗费常数时间的通常模型下,主要操作的时间复杂度如下:
| 操作 | 时间界 |
|---|---|
| 查看最小值或最大值 | |
| 插入,不计数组重新分配 | 最坏情况 |
| 移除最小值或最大值 | 最坏情况 |
| 修改已知位置的键 | 最坏情况 |
| 删除已知位置的元素 | 最坏情况 |
| 查找任意键 | 最坏情况 |
| 自底向上建堆 | |
| 拼接两个堆后重新建堆以完成合并 |
存储 个元素需要 空间。迭代式上浮和下沉使用 辅助空间。递归实现则可能使用 的调用栈空间。
这些界不包含存储对象本身带来的开销。比较长字符串或移动大型记录,可能使名义上为常数时间的步骤变得更加昂贵。
应用
优先队列
优先队列是一种抽象数据类型,规定了插入、移除最高优先级元素等操作;二叉堆则是它的一种具体实现。
基于堆的优先队列可用于事件仿真、任务选择和处理器调度系统。在这些系统中,下一个要处理的项目由优先级决定,而非由到达顺序决定。
它们也用于图算法。迪ijkstra算法可以使用最小堆选出暂定距离最小的下一个顶点,而A星搜索则按照估计的路径总成本排列候选项。具体实现可以支持直接更新优先级,也可以插入修订后的条目,并在移除时忽略过时条目。
堆排序
堆排序先构建最大堆,然后反复将根元素与当前有效堆中的最后一个元素交换,缩小有效区域,再恢复堆序。最终得到升序序列。
这种方法是一种排序算法,最坏情况下的运行时间为 。其常规迭代实现使用 辅助空间,但并不稳定:键相等的元素可能改变相对顺序。
选择与归并
大小为 的堆可以保留数据流中迄今遇到的最大 个元素。最小堆可直接提供所保留元素中的最小值,便于判断新元素是否应替换它。当 时,处理 个元素需要 时间和 存储空间。
归并 个有序序列时,可以用最小堆保存每个序列中下一个可用的元素。每次取出最小元素后,算法将该元素在原序列中的后继插入堆中。对于总计 个元素且 的情况,这种方法需要 时间。
局限与实现注意事项
不支持高效的通用查找。 堆序不足以支持在底层数组中进行二分查找。搜索树通常更适合支持有序遍历和范围查询。
本身不具备稳定性。 优先级相等的元素不一定按插入顺序移除。稳定优先队列可以将优先级与插入序号组成二元组进行比较。
可变键需要修复。 在外部修改键而不恢复堆序,可能导致后续操作失效。接口可以禁止此类修改,或要求显式执行更新操作。
比较规则必须一致。 正确性依赖于一致的顺序关系。对于浮点非数(NaN)等值,如果语言的普通比较无法提供所需的顺序关系,就必须进行显式处理。
合并并不特别高效。 拼接两个堆数组并重新建堆,所需时间与它们的总大小成线性关系。这适合批量合并,但无法提供某些其他堆结构所支持的高效合并操作。
数组位置不是稳定的身份标识。 插入、移除和修复都会移动元素。外部对位置的引用需要维护,而数组重新分配还可能使直接内存引用失效。
历史与相关结构
J. W. J. 威廉姆斯于 1964 年在堆排序的相关工作中提出了二叉堆。同年,弗洛伊德发表了一种改进的堆排序方法,其中包含自底向上的建堆技术,成为标准线性时间建堆过程的基础。
二叉堆是d 叉堆的特例;在 d 叉堆中,每个节点最多可以有 个子节点。更大的分支因子可以降低树高,但下沉时需要检查更多子节点。
其他优先队列结构采用了不同的权衡。二项堆支持高效合并,而斐波那契堆则为减小键等操作提供了更优的摊还复杂度界。二叉堆仍被广泛使用,因为它的数组表示紧凑、算法简单,而且实际开销相对较低。
“堆”(heap)一词也指用于动态内存分配的区域。这一含义与二叉堆数据结构不同;内存分配器不一定将其存储空间组织为二叉堆。