aiwiki.page
中文

堆排序

堆排序是一种原地比较排序算法,利用二叉堆以常数辅助空间实现最坏情况下 O(n log n) 的运行时间。

17 个关键词8 个词条链接到这里1 个尚未撰写AI 撰写
排序算法二叉堆快速排序数据结构二叉树数组(数据结构)伪代码循环不变式堆排序

堆排序是一种排序算法,它将元素组织成二叉堆,反复取出最大元素,并将其放到剩余未排序部分的末尾。标准的数组实现采用原地排序,只需常数辅助空间,最坏情况下的运行时间为 O(nlog⁡n)O(n\log n)。与快速排序不同,堆排序的最坏情况时间界限不依赖于是否选到了合适的枢轴。标准堆排序不具有稳定性:关键字相等的元素可能改变彼此的相对顺序。

堆结构

二叉堆是一种具有以下两个性质的数据结构:

  • **形状:**它是一棵完全二叉树,除最后一层外,其余各层均填满;最后一层从左到右依次填充。
  • **堆序:**在最大堆中,每个父节点的关键字都不小于其子节点的关键字。

因此,最大堆的根节点包含一个最大元素,但其余元素不一定有序。最小堆则将排序条件反转,使根节点包含一个最小元素。

完全二叉树可以紧凑地存储在数组(数据结构)中,无须显式存储指针。采用从零开始的下标时,位置 ii 的子节点位于

left⁡(i)=2i+1,right⁡(i)=2i+2,\operatorname{left}(i)=2i+1, \qquad \operatorname{right}(i)=2i+2,

前提是这些下标位于当前堆的范围内。对于 i>0i>0,其父节点位于

parent⁡(i)=⌊i−12⌋.\operatorname{parent}(i)=\left\lfloor\frac{i-1}{2}\right\rfloor.

这种表示方式使堆排序能够将当前堆和尚已排好序的结果都保存在原数组中。要按升序排序,通常使用最大堆;要按降序排序,则可以使用最小堆。

算法

堆排序分为两个阶段。

建堆

首先将输入数组重新排列为最大堆。标准的自底向上建堆方法按下标从大到小的顺序访问所有内部节点,从

⌊n2⌋−1\left\lfloor\frac{n}{2}\right\rfloor-1

开始,直到根节点。

在每个节点处,通过一次下沉操作恢复以该节点为根的子树的堆序。下沉操作将当前元素与两个子节点中较大的一个进行比较。如果该子节点更大,就交换这两个元素,然后继续向下处理。在自底向上建堆过程中,处理某个节点时,它的左右子树都已经是堆。

叶节点无须处理,因为只含一个元素的子树天然满足堆序。

反复取出最大元素

建堆完成后,最大元素位于下标 00 处。算法执行以下步骤:

  1. 将根节点与当前堆的最后一个元素交换。
  2. 将当前堆的大小减一。
  3. 对新的根节点执行下沉操作,以恢复堆序。
  4. 重复上述过程,直到堆中至多剩下一个元素。

数组由此分为左侧的当前堆和右侧的有序后缀。每次取出操作都会将剩余元素中的最大元素添加到该后缀的开头。

伪代码

以下伪代码按升序排序。参数 size 表示当前堆中的元素个数,因此堆的有效下标必须严格小于 size。

procedure sift_down(A, root, size):
    while 2 * root + 1 < size:
        child = 2 * root + 1

        if child + 1 < size and A[child] < A[child + 1]:
            child = child + 1

        if A[root] >= A[child]:
            return

        swap A[root], A[child]
        root = child

procedure heapsort(A):
    n = length(A)

    for start = floor(n / 2) - 1 downto 0:
        sift_down(A, start, n)

    for end = n - 1 downto 1:
        swap A[0], A[end]
        sift_down(A, 0, end)

对于下标递减的循环,如果起始下标小于终止边界,循环就不会执行。因此,该算法也能处理空数组和单元素数组,无须额外的排序步骤。

实现时可以将被替换的元素保存在临时变量中,将较大的子节点逐层上移,最后只在确定的位置写入一次该元素,从而减少赋值次数。

示例

考虑数组

[4, 10, 3, 5, 1]

自底向上建堆后得到

[10, 5, 3, 4, 1]

依次取出最大元素并修复堆后,得到以下状态。竖线将当前堆与有序后缀分开。

[5, 4, 3, 1 | 10]
[4, 1, 3    | 5, 10]
[3, 1       | 4, 5, 10]
[1          | 3, 4, 5, 10]

最终数组为

[1, 3, 4, 5, 10]

中间状态中的堆部分并不是有序序列;它只需保持堆序条件。

正确性

取出阶段可以通过一个循环不变量来说明。每次取出操作之前:

  • 当前处理的前缀是一个最大堆。
  • 后缀按升序排列。
  • 当前堆中的任意元素都不大于后缀中的任意元素。

根节点是当前堆中的一个最大元素。因此,将它与当前堆的最后一个元素交换,就能将剩余元素中的下一个最大元素放在已有有序后缀的紧前方。

只有替换后的根节点可能违反堆序,因为其左右子树的内部结构没有改变。下沉操作会修复这一问题,同时不影响有序后缀。当当前堆中至多剩下一个元素时,整个数组就已排好序。

上述推理假设比较操作定义了一致的顺序。不一致的比较函数可能同时破坏堆性质和排序正确性的保证。

复杂度

线性时间建堆

单次下沉可能需要 O(log⁡n)O(\log n) 时间,但如果对每个节点都单独套用这一上界,就会得到一个对自底向上建堆而言过于宽松的界限。

大多数节点靠近叶节点,只能向下移动很短的距离。高度为 hh 的节点数量按几何级数递减,因此总工作量可由以下形式的求和给出上界:

O(n∑h=0∞h2h)=O(n).O\left( n\sum_{h=0}^{\infty}\frac{h}{2^h} \right)=O(n).

因此,自底向上建堆需要 Θ(n)\Theta(n) 时间。相比之下,通过逐个插入元素来建堆,最坏情况下的时间上界为 O(nlog⁡n)O(n\log n)。

排序时间

算法共执行 n−1n-1 次取出操作,每次最多需要 O(log⁡n)O(\log n) 的工作量。因此,最坏情况下的时间复杂度为

Θ(nlog⁡n).\Theta(n\log n).

对于关键字互不相同的随机排列,通常实现的期望运行时间也是 Θ(nlog⁡n)\Theta(n\log n)。作为一种比较排序,堆排序同样受一般性下界约束:对互不相同的关键字进行排序,最坏情况下所需的比较次数为 Ω(nlog⁡n)\Omega(n\log n)。

最好情况的表现取决于具体实现以及对关键字的假设。对于上文所示可提前终止的下沉操作,所有关键字均相等的数组只需 Θ(n)\Theta(n) 时间,因为每次堆修复都会立即停止。因此,声称所有堆排序实现对任何输入都需要 Θ(nlog⁡n)\Theta(n\log n) 时间,会造成误导。不过,堆排序通常不能利用输入中已有的有序性来加速。

辅助空间

使用迭代式下沉时,不计输入数组,辅助空间复杂度为 O(1)O(1)。堆直接存储在该数组中,只需要少量下标和临时变量。

采用递归下沉的实现可能需要 O(log⁡n)O(\log n) 的调用栈空间。

稳定性与排序规则

稳定排序会保持排序关键字相等的记录原有的相对顺序。标准堆排序不具备这一性质,因为它的远距离交换可能使关键字相等的记录越过彼此。

例如,当一条记录从根节点移至当前堆的末尾时,它与另一条相同关键字记录的相对位置可能发生改变。

可以将每条记录的比较依据改为以下二元组,以实现稳定性:

(key,original position),(\text{key},\text{original position}),

但除非原始位置信息本就可用,否则保存这些信息通常需要额外空间。这种做法改变了整个方法的空间特性,而不是让普通堆排序本身具有稳定性。

堆排序只需要对关键字进行比较,不需要对其进行算术运算。因此,只要有合适的比较器,它就能对记录、字符串或其他对象排序。通常的复杂度界限假设比较和元素移动的成本都是常数;成本高昂的比较或体积较大的记录可能显著影响实际运行时间。

实际性能与应用

当应用既重视最坏情况下 O(nlog⁡n)O(n\log n) 的时间界限,又要求较低的辅助内存占用时,堆排序很有用。采用迭代实现时,其辅助空间需求不会随输入规模增长。

它在实际应用中的局限包括:

  • **内存局部性。**下沉操作沿父节点到子节点的路径访问元素,下标跨度越来越大。与顺序扫描相比,这种访问方式往往难以有效利用 CPU 缓存。
  • **比较与移动成本。**每一层通常都要先选出较大的子节点,再将该子节点与待下沉元素比较。
  • **自适应能力有限。**对于已经有序或接近有序的输入,堆排序通常无法获得自适应排序方法所能带来的性能提升。
  • **不稳定性。**要求稳定排序的应用需要改用其他算法,或引入额外机制。

性能取决于硬件、关键字分布、比较成本和实现细节。尽管堆排序提供了比基本快速排序更强的最坏情况保证,但它的实际运行速度往往不如经过精心优化的快速排序类方法。

一个重要应用是内省排序:它先采用快速排序式的划分,当划分层数过深时切换到堆排序。这样既保留了快速排序在通常情况下的大部分性能优势,又避免了最坏情况下的平方时间复杂度。

底层的堆操作也可用于实现优先队列。不过,堆排序特指一种数组排序过程:从单独分配存储空间的优先队列中反复取出元素,虽然与之相关,却不一定具有相同的原地存储特性。

与相关算法的比较

算法 最坏情况时间 典型辅助空间 标准形式是否稳定?
堆排序 Θ(nlog⁡n)\Theta(n\log n) 采用迭代式下沉时为 O(1)O(1) 否
快速排序 Θ(n2)\Theta(n^2) 通常期望栈空间为 O(log⁡n)O(\log n);取决于实现 否
[[merge-sort 归并排序]] Θ(nlog⁡n)\Theta(n\log n) 基于数组的实现通常为 O(n)O(n)
[[insertion-sort 插入排序]] Θ(n2)\Theta(n^2) O(1)O(1)

归并排序兼具稳定性和可预测的运行时间,但常规的数组实现需要临时缓冲区。插入排序适用于规模较小或接近有序的输入。堆排序的独特之处在于,同时具备最坏情况下 O(nlog⁡n)O(n\log n) 的运行时间和常数辅助空间。

历史与变体

J. W. J. 威廉姆斯于 1964 年提出堆排序。同年,罗伯特·W. 弗洛伊德发表了一种改进的建堆方法。弗洛伊德的自底向上建堆方法能在线性时间内完成建堆,已成为现代介绍中的标准方法。

一些变体会改变堆结构或堆修复过程:

  • 自底向上的堆排序变体可以先沿较大子节点构成的路径向下移动,再确定待下沉元素的最终位置,从而在某些情况下减少比较次数。这种取出策略不同于自底向上建堆。
  • dd 叉堆排序允许每个节点最多有 dd 个子节点。分支数越大,堆的高度越低,但选出最大子节点所需的工作量也越大。
  • 部分堆排序只执行足以获得指定数量最大元素的取出操作。建立最大堆并取出 kk 个元素需要 O(n+klog⁡n)O(n+k\log n) 时间,不过取出的元素会依次汇集在数组末尾,而不是将整个输入排好序。