第6章 堆排序

导读

堆排序（Heapsort）是一种基于堆（Heap）数据结构的比较排序算法。它结合了插入排序的空间效率和归并排序的时间效率——既是原地排序，又具有O(n log n)的最坏情况时间复杂度。堆排序的核心是堆这种数据结构，它不仅用于排序，还是实现优先队列的高效工具。

本章将详细介绍堆的定义和性质、堆排序算法、优先队列的实现，以及堆在其他算法中的应用。我们还将分析堆排序的性能特点，并与归并排序和快速排序进行比较。

核心概念详解

6.1 堆的定义

堆（Heap）是一种特殊的完全二叉树，满足堆性质：

最大堆（Max-Heap）：每个节点的值都大于或等于其子节点的值。因此，根节点是堆中的最大值。

最小堆（Min-Heap）：每个节点的值都小于或等于其子节点的值。因此，根节点是堆中的最小值。

完全二叉树：除了最后一层，其他层都是满的，且最后一层的节点都靠左排列。

数组表示：

堆可以用数组高效地表示。对于下标为i的节点：

• 父节点：PARENT(i) = ⌊i/2⌋
• 左子节点：LEFT(i) = 2i
• 右子节点：RIGHT(i) = 2i + 1

这种表示方法不需要指针，空间效率高，且访问父节点和子节点只需O(1)时间。

6.2 维护堆的性质

MAX-HEAPIFY过程：

当某个节点的值小于其子节点时，需要通过下沉操作恢复堆性质。

MAX-HEAPIFY(A, i)
    l = LEFT(i)
    r = RIGHT(i)
    largest = i
    if l ≤ A.heap-size and A[l] > A[i]
        largest = l
    if r ≤ A.heap-size and A[r] > A[largest]
        largest = r
    if largest ≠ i
        交换A[i]和A[largest]
        MAX-HEAPIFY(A, largest)

时间复杂度：O(h)，其中h为节点i的高度。对于高度为h的树，最多需要h次交换。在n个节点的堆中，树高为log n，因此MAX-HEAPIFY的时间为O(log n)。

6.3 建堆

BUILD-MAX-HEAP过程：

将无序数组转换为最大堆。

BUILD-MAX-HEAP(A)
    A.heap-size = A.length
    for i = ⌊A.length/2⌋ downto 1
        MAX-HEAPIFY(A, i)

为什么从⌊n/2⌋开始：

叶子节点没有子节点，自然满足堆性质。数组中下标从⌊n/2⌋+1到n的节点都是叶子节点，因此只需从⌊n/2⌋开始向下处理。

时间复杂度分析：

虽然直观上看是O(n log n)（n/2次调用，每次O(log n)），但更精确的分析表明是O(n)。

证明（使用聚合分析）：

• 高度为h的节点最多有⌈n/2^(h+1)⌉个
• 每个高度为h的节点的MAX-HEAPIFY代价为O(h)
• 总代价 ≤ Σ(h=0 to log n) ⌈n/2^(h+1)⌉ · O(h)
• = O(n) · Σ(h=0 to ∞) h/2^h
• = O(n) · 2 = O(n)

因此，建堆的时间复杂度为O(n)。

6.4 堆排序算法

HEAPSORT过程：

HEAPSORT(A)
    BUILD-MAX-HEAP(A)
    for i = A.length downto 2
        交换A[1]和A[i]
        A.heap-size = A.heap-size - 1
        MAX-HEAPIFY(A, 1)

工作原理：

建堆：将数组转换为最大堆，O(n)

排序：重复n-1次：

- 将堆顶（最大值）与堆的最后一个元素交换

- 堆大小减1

- 对新堆顶执行MAX-HEAPIFY

时间复杂度：

• 建堆：O(n)
• n-1次MAX-HEAPIFY：每次O(log n)，共O(n log n)
• 总时间：O(n log n)

空间复杂度：O(1)，原地排序。

稳定性：不稳定排序。

6.5 优先队列

堆是實現优先队列（Priority Queue）的理想数据结构。

最大优先队列支持的操作：

INSERT(S, x)：将元素x插入集合S

- 将x放在数组末尾

- 通过上浮操作恢复堆性质

- 时间：O(log n)

MAXIMUM(S)：返回S中具有最大关键字的元素

- 直接返回A[1]

- 时间：O(1)

EXTRACT-MAX(S)：去掉并返回S中具有最大关键字的元素

- 返回A[1]

- 将最后一个元素移到堆顶

- MAX-HEAPIFY

- 时间：O(log n)

INCREASE-KEY(S, x, k)：将元素x的关键字增加到k

- 更新x的值

- 通过上浮操作恢复堆性质

- 时间：O(log n)

应用：

• 作业调度：优先级高的作业先执行
• 事件驱动模拟：按时间顺序处理事件
• Dijkstra最短路径算法
• Huffman编码

6.6 堆排序的性能分析

最好、最坏、平均情况：

堆排序的所有情况时间复杂度都是O(n log n)。这是因为：

• 建堆总是O(n)
• 每次MAX-HEAPIFY总是O(log n)
• 共执行n-1次MAX-HEAPIFY

与归并排序比较：

• 都是O(n log n)
• 堆排序是原地的，归并排序需要O(n)额外空间
• 归并排序是稳定的，堆排序不稳定
• 归并排序的常数因子更小，实际更快

与快速排序比较：

• 快速排序平均更快（常数因子小，缓存友好）
• 堆排序最坏情况O(n log n)，快速排序最坏O(n²)
• 快速排序不是原地（递归栈空间），但堆排序完全原地

6.7 堆的变体

二项堆（Binomial Heap）：

• 支持高效的合并操作O(log n)
• 由多棵二项树组成
• 用于需要频繁合并优先队列的场景

斐波那契堆（Fibonacci Heap）：

• 摊还分析下的更优时间复杂度
• INSERT: O(1)摊还
• EXTRACT-MIN: O(log n)摊还
• DECREASE-KEY: O(1)摊还
• 用于优化图算法（如Dijkstra、Prim）

左偏树（Leftist Tree）：

• 一种可合并堆
• 合并操作O(log n)

6.8 堆排序的优化

Floyd优化：

在MAX-HEAPIFY中，先找到元素应该放置的位置，然后一次性移动，减少交换次数。

Bottom-up Heapsort：

在堆排序的排序阶段，利用堆的部分有序性优化MAX-HEAPIFY。

Introsort中的堆排序：

当快速排序递归深度超过阈值时，切换到堆排序以保证O(n log n)的最坏情况。

6.9 堆与其他数据结构的关系

堆与二叉搜索树：

• 堆：父节点大于/小于子节点，但不保证左右子树的顺序
• BST：左子树 < 根 < 右子树
• 堆不支持高效的搜索，BST不支持高效的最大/最小值操作

堆与平衡树：

• 平衡树支持O(log n)的搜索、插入、删除
• 堆只保证最大值/最小值在根，不支持高效搜索
• 堆的插入和删除最大值更高效

重要知识点

知识点1：O(n)建堆的证明

O(n)建堆是堆排序的关键性质。证明使用聚合分析：

• 高度为h的节点最多有⌈n/2^(h+1)⌉个
• 每个节点的代价为O(h)
• 总代价 = Σ ⌈n/2^(h+1)⌉ · h ≤ n · Σ h/2^h = O(n)

知识点2：堆的数组表示的优势

数组表示堆的优势：

• 不需要指针，空间效率高
• 父子关系的计算只需简单算术
• 连续的内存布局对缓存友好
• 实现简单

知识点3：优先队列的抽象数据类型

优先队列是一种抽象数据类型，定义了一组操作。堆是实现优先队列的一种数据结构。理解抽象数据类型和具体实现的区别是重要的。

知识点4：堆排序的不稳定性

堆排序是不稳定的，因为在MAX-HEAPIFY过程中，相等元素的相对顺序可能改变。如果需要稳定排序，应选择归并排序或插入排序。

知识点5：堆在实际系统中的应用

堆在实际系统中广泛应用：

• 操作系统进程调度
• 网络带宽管理
• 数据库查询优化
• 事件驱动系统

常见误区

误区1：堆排序总是比快速排序快

实际上，由于缓存友好性和更小的常数因子，快速排序在大多数情况下比堆排序更快。堆排序的优势在于最坏情况保证和原地性。

误区2：堆可以用于高效搜索

堆只保证根节点是最大值（或最小值），不支持高效的任意元素搜索。搜索需要O(n)时间。如果需要搜索，应使用二叉搜索树或哈希表。

误区3：建堆需要O(n log n)时间

这是一个常见误解。虽然建堆调用了n/2次MAX-HEAPIFY，但由于大部分调用发生在低层节点（代价小），总时间实际上是O(n)。

误区4：堆只能用于排序

堆的应用远不止排序。优先队列是堆最重要的应用之一，广泛用于作业调度、图算法、事件模拟等场景。

误区5：最大堆和最小堆可以互相转换

最大堆和最小堆的结构不同，不能简单地通过修改比较操作来转换。需要重新建堆。

实践应用

应用1：操作系统中的进程调度

操作系统使用优先队列（通常基于堆）管理进程：

• 高优先级进程先执行
• 动态调整进程优先级
• 时间片轮转结合优先级

应用2：Dijkstra最短路径算法

Dijkstra算法使用最小堆优化：

• 维护待处理节点的最小距离
• 每次取出距离最小的节点
• 使用DECREASE-KEY更新邻居距离
• 使用斐波那契堆可将时间优化到O(E + V log V)

应用3：Huffman编码

Huffman编码使用最小堆构建最优前缀码：

• 每次取出两个频率最小的节点合并
• 重复直到只剩一个节点
• 时间复杂度O(n log n)

应用4：Top-K问题

在大规模数据中找最大/最小的K个元素：

• 维护大小为K的最小堆
• 遍历数据，维护堆中的K个最大元素
• 时间复杂度O(n log K)

应用5：中位数维护

使用两个堆维护动态数据流的中位数：

• 最大堆存储较小的一半
• 最小堆存储较大的一半
• 保持两个堆大小平衡
• 插入O(log n)，查询中位数O(1)

6.10 堆排序的详细正确性证明

MAX-HEAPIFY的正确性：

循环不变式（递归版本）：在调用MAX-HEAPIFY(A, i)之前，以LEFT(i)和RIGHT(i)为根的子树都是最大堆。

证明：

• 如果A[i]已经是最大的，不需要任何操作，性质保持
• 如果A[i]不是最大的，交换A[i]和最大的子节点，然后递归处理子节点
• 递归调用前，子节点的子树仍然是最大堆（未被修改）
• 递归保证了交换后的子树重新成为最大堆

BUILD-MAX-HEAP的正确性：

循环不变式：在for循环的每次迭代开始时，每个下标i+1, i+2, ..., n的节点都是某个最大堆的根。

• 初始化：i = ⌊n/2⌋时，下标⌊n/2⌋+1到n都是叶子节点，自然是最大堆
• 保持：每次MAX-HEAPIFY(A, i)将节点i变为最大堆的根，因为它的子节点已经是最大堆的根
• 终止：i = 1时，节点1成为最大堆的根，整个数组是最大堆

6.11 堆的变体深入分析

二项堆的详细结构：

二项堆由多棵二项树组成。二项树Bₖ的定义：

• B₀是单节点
• Bₖ由两棵Bₖ₋₁组成，一棵的根是另一棵根的左孩子

Bₖ有2ᵏ个节点，高度为k。二项堆中最多有⌊log n⌋+1棵二项树。

操作复杂度：

• INSERT：O(log n)摊还
• EXTRACT-MIN：O(log n)
• MERGE：O(log n)
• DECREASE-KEY：O(log n)

斐波那契堆的详细分析：

斐波那契堆是松弛堆，允许延迟维护某些性质。

关键操作的摊还代价：

• INSERT：O(1)
• MERGE：O(1)
• EXTRACT-MIN：O(log n)摊还
• DECREASE-KEY：O(1)摊还
• DELETE：O(log n)摊还

斐波那契堆的核心优势在于DECREASE-KEY的O(1)摊还代价。这使得Dijkstra算法的时间从O(E log V)优化到O(E + V log V)。

6.12 堆在实际系统中的实现细节

数组索引的选择：

• 从1开始：PARENT(i) = i/2，LEFT(i) = 2i，RIGHT(i) = 2i+1
• 从0开始：PARENT(i) = (i-1)/2，LEFT(i) = 2i+1，RIGHT(i) = 2i+2

从1开始更简洁，但从0开始更符合编程语言习惯。

堆化（Heapify）的迭代版本：

递归版本的MAX-HEAPIFY可以改写为迭代版本，避免递归开销：

MAX-HEAPIFY-ITERATIVE(A, i)
    while TRUE
        l = LEFT(i), r = RIGHT(i)
        largest = i
        if l ≤ heap-size and A[l] > A[largest]
            largest = l
        if r ≤ heap-size and A[r] > A[largest]
            largest = r
        if largest == i
            break
        交换A[i]和A[largest]
        i = largest

多线程堆：

在多线程环境中，堆操作需要加锁。d-堆（每个节点有d个子节点）可以减少树的高度，降低EXTRACT-MIN的深度，但增加INSERT的上浮代价。

本章小结

本章深入介绍了堆排序和优先队列。我们学习了：

堆的定义和性质：堆是一种完全二叉树，满足堆性质。可以用数组高效表示，父子关系的计算只需简单算术。

堆排序算法：包括MAX-HEAPIFY、BUILD-MAX-HEAP和HEAPSORT。时间复杂度O(n log n)，空间O(1)。正确性通过循环不变式证明。

O(n)建堆：通过聚合分析证明建堆时间为O(n)。关键观察是大部分节点在低层，MAX-HEAPIFY代价小。

优先队列：使用堆实现，支持INSERT、MAXIMUM、EXTRACT-MAX、INCREASE-KEY操作。

堆的变体：二项堆（高效合并）和斐波那契堆（O(1)摊还DECREASE-KEY）。

性能比较：堆排序与归并排序、快速排序的对比。堆排序最坏O(n log n)但常数因子大。

应用：进程调度、Dijkstra算法、Huffman编码、Top-K问题、中位数维护等。

堆排序是一种优雅而实用的排序算法，堆数据结构在算法设计中有着广泛的应用。理解堆的原理和实现是算法学习的重要一环。

关键术语

思考题

证明：在n个元素的堆中，叶子节点的个数为⌈n/2⌉。

设计一个算法，在O(log n)时间内合并两个大小分别为m和n的最大堆（m << n）。

分析使用最小堆实现优先队列时，DECREASE-KEY操作的时间复杂度。

设计一个算法，使用堆在O(n log k)时间内找到n个元素中第k大的元素。