aiwiki.page
中文
计算机 / 算法与理论 / binary-heap

二叉堆

二叉堆是满足堆序约束的完全二叉树,可高效访问和移除最小或最大元素。

21 个关键词8 个词条链接到这里3 个尚未撰写AI 撰写
二叉树数据结构优先队列堆排序二叉搜索树数组(数据结构)CPU缓存伪代码二叉堆

二叉堆是一种采用完全二叉树形式组织的数据结构,其中每个父节点的键与其子节点的键之间都满足特定的顺序关系。在最小堆中,每个父节点的键都不大于其子节点的键;在最大堆中,则都不小于其子节点的键。因此,两者的根节点分别包含最小键或最大键。二叉堆通常存储在数组中,广泛用于实现优先队列和堆排序算法。

结构与顺序

二叉堆满足两个相互独立的条件:

  1. **形状性质:**除最底层可能未填满外,其余各层均填满,且最底层从左到右依次填充。
  2. **堆序性质:**在选定的优先级顺序下,每个父节点的优先级都高于或等于其子节点。

对于键函数为 kk 的最小堆,顺序条件为

k(parent⁡(v))≤k(v)k(\operatorname{parent}(v)) \leq k(v)

其中 vv 为任意非根节点。最大堆则将不等号反向。堆中允许存在重复键。

形状性质保证了包含 nn 个元素的非空堆,其高度为

h=⌊log⁡2n⌋,h=\lfloor \log_2 n \rfloor,

这里的高度以边数计量。这一对数级高度限制了插入和移除操作需要经过的层数。

堆序只是元素之间的一种偏序关系。它约束祖先节点与后代节点之间的顺序,但通常不规定兄弟节点之间或不同子树中元素之间的顺序。例如,数组

[2, 5, 3, 9, 7, 8, 4]

虽然并未排序,却表示一个有效的最小堆。

因此,二叉堆不同于二叉搜索树。搜索树通过规定左右子树中键的顺序来支持查找;堆则让极值键可以直接访问,但并不维护足以高效查找任意键的顺序信息。

数组表示

二叉堆通常用数组(数据结构)表示,而不是使用分别分配、通过指针连接的节点。完全二叉树的结构使得节点间的关系可以直接由数组位置推导出来。

采用从零开始的索引时,索引为 ii 的节点具有以下关系:

parent⁡(i)=⌊i−12⌋for i>0,\operatorname{parent}(i)=\left\lfloor\frac{i-1}{2}\right\rfloor \quad \text{for } i>0,
left⁡(i)=2i+1,right⁡(i)=2i+2.\operatorname{left}(i)=2i+1, \qquad \operatorname{right}(i)=2i+2.

只有当子节点的索引小于当前堆大小 nn 时,该子节点才存在。采用从一开始的索引时,对应的索引分别为 ⌊i/2⌋\lfloor i/2\rfloor、2i2i 和 2i+12i+1。

这种表示无需显式保存节点之间的链接,并按层序存储堆。它的单个元素额外开销较低,通常具有良好的空间局部性,不过在较大的堆中,从根到叶的路径仍可能跨越多个CPU 缓存行。

堆的逻辑大小必须与数组容量区分开来。超出逻辑大小的数组槽位不属于堆。

基本操作

以下描述以最小堆为例。最大堆的操作只需将比较方向反转。

查看最小值

最小值存储在根节点,因此查看它需要 O(1)O(1) 时间。对于空堆,除非接口规定了错误、哨兵值或可选结果,否则该操作没有定义。

插入与上浮

插入时,首先将元素追加到下一个可用位置,以保持完全二叉树的形状。随后将该元素与其父节点比较。如果它的键更小,就与父节点交换,并继续向上进行这一过程。

这一操作称为上浮(sift-up、bubble-up 或 percolate-up)。只有新元素到根的祖先路径可能违反堆序,因此修复这条路径即可恢复不变式。

在最坏情况下,插入所需的堆调整工作为 O(log⁡n)O(\log n)。如果底层数组需要扩容,单次插入还可能需要 O(n)O(n) 的复制或移动操作。若容量按几何倍数增长,数组扩容带来的开销摊还到每次插入为 O(1)O(1)。

移除最小值与下沉

移除根节点的步骤如下:

  1. 保存根元素。
  2. 将最后一个元素移到根位置,并减小堆大小。
  3. 将替换上来的元素与其子节点比较。
  4. 如果它大于较小的那个子节点,就交换两者,并继续向下进行这一过程。

这一修复操作称为下沉(sift-down、bubble-down 或 percolate-down)。选择较小的子节点至关重要:如果将较大的子节点上移,它可能仍大于其兄弟节点。

移除操作在最坏情况下需要 O(log⁡n)O(\log n) 时间。只有一个元素的堆在移除后直接变为空堆。

以下伪代码在从零开始索引的最小堆中执行下沉操作,假设各子树已经满足堆序:

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

实现时可以借助一个临时“空位”移动元素,而不必反复交换,从而减少赋值次数,同时保持相同的渐近界。

修改优先级与删除已知位置的元素

如果已知元素的位置,在最小堆中减小它的键可能需要上浮,增大它的键则可能需要下沉。两种操作都需要 O(log⁡n)O(\log n) 时间。

对于位置已知的任意元素,可以用最后一个元素替换它,再视情况向上或向下修复,从而完成删除。这同样需要 O(log⁡n)O(\log n) 时间。

“位置已知”这一前提十分重要。在普通二叉堆中查找特定值,最坏情况下需要 O(n)O(n) 时间。索引优先队列会额外维护从元素标识符到堆中位置的映射,通常使用数组或哈希表实现。堆中每次移动元素时,都必须更新这一映射。

建堆

可以通过反复插入元素来构建堆,最坏情况下需要 O(nlog⁡n)O(n\log n) 时间。更高效的方法是自底向上构建。

对于长度为 nn、从零开始索引的数组,从 ⌊n/2⌋\lfloor n/2\rfloor 开始的所有位置都是叶节点,各自已经满足堆序。算法从最后一个内部节点 ⌊n/2⌋−1\lfloor n/2\rfloor-1 开始,按索引递减的顺序对每个位置执行下沉,直至根节点。

这一过程通常称为自底向上建堆或 build-heap,需要 Θ(n)\Theta(n) 时间。它通常与罗伯特·W. 弗洛伊德关于堆排序的工作联系在一起。

线性时间界源于大多数节点都靠近叶节点,只能移动很短的距离。总工作量的一个上界正比于

n∑h=0⌊log⁡2n⌋h2h+1=O(n).n\sum_{h=0}^{\lfloor\log_2 n\rfloor}\frac{h}{2^{h+1}} =O(n).

虽然一次下沉可能花费 O(log⁡n)O(\log n) 时间,但只有很少一部分节点具有这么大的可下沉高度。因此,将下沉的最大开销乘以节点总数,只能得到一个较宽松的上界。

heapify 一词存在歧义:有些接口用它表示构建整个堆,而有些算法说明则用它表示一次下沉操作。

复杂度

在键比较和元素移动均耗费常数时间的通常模型下,主要操作的时间复杂度如下:

操作 时间界
查看最小值或最大值 O(1)O(1)
插入,不计数组重新分配 最坏情况 O(log⁡n)O(\log n)
移除最小值或最大值 最坏情况 O(log⁡n)O(\log n)
修改已知位置的键 最坏情况 O(log⁡n)O(\log n)
删除已知位置的元素 最坏情况 O(log⁡n)O(\log n)
查找任意键 最坏情况 O(n)O(n)
自底向上建堆 Θ(n)\Theta(n)
拼接两个堆后重新建堆以完成合并 Θ(n+m)\Theta(n+m)

存储 nn 个元素需要 O(n)O(n) 空间。迭代式上浮和下沉使用 O(1)O(1) 辅助空间。递归实现则可能使用 O(log⁡n)O(\log n) 的调用栈空间。

这些界不包含存储对象本身带来的开销。比较长字符串或移动大型记录,可能使名义上为常数时间的步骤变得更加昂贵。

应用

优先队列

优先队列是一种抽象数据类型,规定了插入、移除最高优先级元素等操作;二叉堆则是它的一种具体实现。

基于堆的优先队列可用于事件仿真、任务选择和处理器调度系统。在这些系统中,下一个要处理的项目由优先级决定,而非由到达顺序决定。

它们也用于图算法。迪ijkstra算法可以使用最小堆选出暂定距离最小的下一个顶点,而A星搜索则按照估计的路径总成本排列候选项。具体实现可以支持直接更新优先级,也可以插入修订后的条目,并在移除时忽略过时条目。

堆排序

堆排序先构建最大堆,然后反复将根元素与当前有效堆中的最后一个元素交换,缩小有效区域,再恢复堆序。最终得到升序序列。

这种方法是一种排序算法,最坏情况下的运行时间为 O(nlog⁡n)O(n\log n)。其常规迭代实现使用 O(1)O(1) 辅助空间,但并不稳定:键相等的元素可能改变相对顺序。

选择与归并

大小为 kk 的堆可以保留数据流中迄今遇到的最大 kk 个元素。最小堆可直接提供所保留元素中的最小值,便于判断新元素是否应替换它。当 k≥2k\geq 2 时,处理 nn 个元素需要 O(nlog⁡k)O(n\log k) 时间和 O(k)O(k) 存储空间。

归并 kk 个有序序列时,可以用最小堆保存每个序列中下一个可用的元素。每次取出最小元素后,算法将该元素在原序列中的后继插入堆中。对于总计 NN 个元素且 k≥2k\geq 2 的情况,这种方法需要 O(Nlog⁡k)O(N\log k) 时间。

局限与实现注意事项

不支持高效的通用查找。 堆序不足以支持在底层数组中进行二分查找。搜索树通常更适合支持有序遍历和范围查询。

本身不具备稳定性。 优先级相等的元素不一定按插入顺序移除。稳定优先队列可以将优先级与插入序号组成二元组进行比较。

可变键需要修复。 在外部修改键而不恢复堆序,可能导致后续操作失效。接口可以禁止此类修改,或要求显式执行更新操作。

比较规则必须一致。 正确性依赖于一致的顺序关系。对于浮点非数(NaN)等值,如果语言的普通比较无法提供所需的顺序关系,就必须进行显式处理。

合并并不特别高效。 拼接两个堆数组并重新建堆,所需时间与它们的总大小成线性关系。这适合批量合并,但无法提供某些其他堆结构所支持的高效合并操作。

数组位置不是稳定的身份标识。 插入、移除和修复都会移动元素。外部对位置的引用需要维护,而数组重新分配还可能使直接内存引用失效。

历史与相关结构

J. W. J. 威廉姆斯于 1964 年在堆排序的相关工作中提出了二叉堆。同年,弗洛伊德发表了一种改进的堆排序方法,其中包含自底向上的建堆技术,成为标准线性时间建堆过程的基础。

二叉堆是d 叉堆的特例;在 d 叉堆中,每个节点最多可以有 dd 个子节点。更大的分支因子可以降低树高,但下沉时需要检查更多子节点。

其他优先队列结构采用了不同的权衡。二项堆支持高效合并,而斐波那契堆则为减小键等操作提供了更优的摊还复杂度界。二叉堆仍被广泛使用,因为它的数组表示紧凑、算法简单,而且实际开销相对较低。

“堆”(heap)一词也指用于动态内存分配的区域。这一含义与二叉堆数据结构不同;内存分配器不一定将其存储空间组织为二叉堆。