堆排序

在前面的章节中，我们系统学习了插入排序和归并排序两种经典的排序算法。插入排序虽然实现简单直观，但其 $\Theta(n^2)$ 的时间复杂度在面对大规模数据时效率低下。 归并排序以其 $\Theta(n \lg n)$ 的渐近时间复杂度展现了优异的性能，然而它需要 $\Theta(n)$ 的额外存储空间来完成合并操作，无法实现原地排序（in-place sorting）。

这一节我们将深入学习一种新的排序算法——堆排序（Heapsort）。堆排序算法巧妙地结合了归并排序的时间效率与插入排序的空间优势，实现了 $\Theta(n \lg n)$ 的时间复杂度和 $O(1)$ 的额外空间复杂度，是一种真正的原地排序算法。堆排序的核心思想在于引入并充分利用了一种重要的数据结构——堆（Heap）。

堆不仅是实现堆排序的基础数据结构，其本身在算法设计中也有着广泛的应用，特别是在实现**优先队列（Priority Queue）**这一抽象数据类型时，堆提供了高效的底层实现方案。

堆数据结构

形式化地，一个（二叉）堆可以被定义为一棵近似完全二叉树（nearly complete binary tree）。这意味着除了最底层外，树的每一层都是完全填充的，且最底层的节点都尽可能地从左到右排列。这种结构上的规整性使得我们可以用一个一维数组来紧凑地表示堆，而无需使用指针或链接结构来维护树形关系。

对于包含 $n$ 个元素的堆，我们使用数组 $A[1..n]$ 来表示，其中 $A[1]$ 存储根节点。上述堆的数组表示为：$[\text{null}, 16, 14, 10, 8, 7, 9, 3, 2, 4, 1]$。注意，为了简化索引计算，我们通常从索引 开始存储堆元素，索引 可以留空或用于其他用途。

在数组表示法中，对于索引为 $i$ 的节点，其父节点、左子节点和右子节点的索引可以通过以下数学关系直接计算得出：

• 父节点索引：$\text{PARENT}(i) = \lfloor i/2 \rfloor$
• 左子节点索引：$\text{LEFT}(i) = 2i$ style J fill:#f00,color:#fff
• 右子节点索引：$\text{RIGHT}(i) = 2i + 1$

堆的性质

堆根据其满足的性质，可以分为两种类型：

最大堆（Max-Heap）：对于除根节点外的任意节点 $i$（$2 \leq i \leq n$），都满足堆序性质（heap property）：$A[\text{PARENT}(i)] \geq A[i]$。形式化地，对于所有满足 $2 \leq i \leq n$ 的节点 ，都有 。这意味着任意节点的值都不超过其父节点的值，因此最大堆中的最大元素必然位于根节点 。

最小堆（Min-Heap）：对于除根节点外的任意节点 $i$（$2 \leq i \leq n$），都满足：$A[\text{PARENT}(i)] \leq A[i]$，即 $A[\lfloor i/2 \rfloor] \leq A[i]$。这意味着任意节点的值都不小于其父节点的值，因此最小堆中的最小元素必然位于根节点 。

在本章中，我们主要使用最大堆来实现堆排序算法。最小堆的实现与最大堆在逻辑上完全对称，只需将比较关系反转即可。

堆的基本操作

在深入堆排序算法之前，我们需要先了解堆的一些基本操作。这些操作构成了堆数据结构的基础，也是实现堆排序的关键组件。

获取父节点、左子节点、右子节点索引：

|
PARENT(i)
    return ⌊i/2⌋
 
LEFT(i)
    return 2*i
 
RIGHT(i)
    return 2*i + 1

判断节点是否为叶子节点：

|
IS-LEAF(A, i)
    return i > ⌊A.heap-size/2⌋

在堆的数组表示中，索引从 $\lfloor n/2 \rfloor + 1$ 到 $n$ 的所有节点都是叶子节点，它们没有子节点。这一性质在构建堆的算法中将被充分利用。

维护堆的性质

MAX-HEAPIFY 是堆操作中最核心的子过程，其作用是维护最大堆的堆序性质。当我们调用 MAX-HEAPIFY(A, i) 时，算法有一个重要的前提假设：以 $\text{LEFT}(i)$ 和 $\text{RIGHT}(i)$ 为根的两棵子树都已经是最大堆。然而，节点 $A[i]$ 本身的值可能小于其某个子节点，从而违反了最大堆性质。

MAX-HEAPIFY(A, i) 的核心思想是让 $A[i]$ 的值在最大堆中"下沉"（sink down），通过与较大的子节点交换位置，逐级向下调整，直到以 $i$ 为根的子树重新满足最大堆性质。

|
MAX-HEAPIFY(A, i)
    l = LEFT(i)
    r = RIGHT(i)
    # 在 A[i], A[l], A[r] 中找出最大的元素
    if l <= A.heap-size and A[l] > A[i]
        largest = l
    else
        largest = i
    if r <= A.heap-size and A[r] > A[largest]
        largest = r

假设我们有一个堆，在索引 $i=2$ 处违反了最大堆性质。

交换后，以节点 $2$ 为根的子树满足了最大堆性质。然而，原有的值 $4$ 被交换到了索引 $4$ 的位置，可能会破坏以节点 $4$ 为根的子树的最大堆性质。因此，算法递归调用 MAX-HEAPIFY(A, 4)，此时 $i = 4$。由于节点 $4$ 是叶子节点（没有子节点），递归调用立即返回，算法终止。

最终，整个堆的堆序性质得到完全恢复。

MAX-HEAPIFY 的复杂度分析

MAX-HEAPIFY 的运行时间分析如下：每次调用执行固定数量的比较操作（最多 $3$ 次）和一次元素交换（$O(1)$ 时间），然后可能进行一次递归调用。递归调用的子树规模取决于以节点 $i$ 为根的子树的结构。

在最坏情况下，当底层节点尽可能满时，递归调用的子树规模最大约为 $2n/3$。因此，MAX-HEAPIFY 的时间复杂度满足递推关系：

$T(n) \leq T(2n/3) + O(1)$

根据主定理（Master Theorem），该递推式的解为 $T(n) = O(\lg n)$。更直观地理解，MAX-HEAPIFY 的操作时间与节点 $i$ 在堆中的高度 $h$ 成正比，而堆的高度为 $\lfloor \lg n \rfloor$，因此时间复杂度为 $O(\lg n)$。

构建最大堆

有了 MAX-HEAPIFY 这一工具，我们就可以将一个无序的数组 $A[1..n]$ 构建成一个最大堆。构建策略采用自底向上（bottom-up）的方法，充分利用堆的结构性质。

我们观察到，在数组表示法中，索引从 $\lfloor n/2 \rfloor + 1$ 到 $n$ 的所有元素都是叶子节点。每个叶子节点本身可以看作是一个只包含一个元素的平凡最大堆（trivial max-heap），因为它们没有子节点，自然满足堆序性质。

因此，我们只需要从第一个非叶子节点 $\lfloor n/2 \rfloor$ 开始，按照从下到上、从右到左的顺序，对每个节点调用 MAX-HEAPIFY，直到处理完根节点 $A[1]$。

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

假设输入数组 $A = [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]$，其中 $n=10$，$\lfloor n\mathrm{/}$。循环从 开始，依次处理节点 。

经过多次循环迭代后，我们构建成的最大堆为：$[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]$。

BUILD-MAX-HEAP 的复杂度分析

BUILD-MAX-HEAP 的时间复杂度分析需要仔细考虑。虽然 MAX-HEAPIFY 的时间复杂度是 $O(\lg n)$，但并非所有节点都需要执行完整的 $\lg n$ 次操作。

对于高度为 $h$ 的节点，MAX-HEAPIFY 最多需要 $h$ 次操作。在包含 $n$ 个元素的堆中，高度为 $h$ 的节点最多有 $\lceil n/2^{h+1} \rceil$ 个。因此，BUILD-MAX-HEAP 的总时间复杂度可以表示为对所有高度 $h$ 从 到 的求和：。

通过数学分析，我们可以将上述表达式简化为 $O(n \sum_{h=0}^{\lfloor \lg n \rfloor} h/2^h)$。由于级数 $\sum_{h=0}^{\infty} h/2^h$ 收敛，该表达式进一步简化为 。

堆排序算法

有了 BUILD-MAX-HEAP 和 MAX-HEAPIFY 这两个基础操作，堆排序算法的实现就水到渠成了。堆排序的核心思想是：首先将输入数组构建成最大堆，然后反复取出堆顶元素（最大值），将其放到数组的末尾，并重新调整堆结构。

|
HEAPSORT(A)
    BUILD-MAX-HEAP(A)
    for i = A.length downto 2
        exchange A[1] with A[i]
        A.heap-size = A.heap-size - 1
        MAX-HEAPIFY(A, 1)

堆排序的复杂度分析

堆排序的时间复杂度分析如下：

• 构建最大堆：BUILD-MAX-HEAP 的时间复杂度为 $O(n)$
• 排序循环：循环执行 $n-1$ 次，每次调用 MAX-HEAPIFY，时间复杂度为 $O(\lg n)$，因此总时间为 $O(n \lg n)$

因此，堆排序的总时间复杂度为 $O(n) + O(n \lg n) = O(n \lg n)$。更精确地，堆排序的时间复杂度为 $\Theta(n \lg n)$，因为即使是最优情况，也需要执行 $$ 次 操作。

堆排序的空间复杂度为 $O(1)$，因为除了输入数组外，算法只需要常数个额外变量（如循环计数器、临时变量等）。因此，堆排序是一种真正的原地排序算法。

堆排序的迭代优化

虽然基本的堆排序已经很高效，但在某些实现中，我们可以使用迭代版本的 MAX-HEAPIFY 来避免递归调用带来的函数调用栈开销。迭代版本的 MAX-HEAPIFY 通常比递归版本更高效，特别是在堆规模较大时：

|
MAX-HEAPIFY-ITERATIVE(A, i)
    while true
        l = LEFT(i)
        r = RIGHT(i)
        largest = i
        if l <= A.heap-size and A[l] > A[largest]
            largest = l
        if r <= A.heap-size and A[r] > A[largest]
            largest 

迭代版本的 MAX-HEAPIFY 在功能上与递归版本完全等价，但避免了递归调用的开销，在实际应用中通常具有更好的性能表现。

堆排序与其他排序算法的比较

为了全面评估堆排序的性能特征，我们将其与其他经典排序算法进行比较：

练习与思考

1. 堆的基本操作实现：实现一个完整的最大堆类，包括插入元素、删除最大元素、查找最大元素等基本操作，并分析每个操作的时间复杂度。

2. 最小堆排序：实现最小堆排序算法，即使用最小堆来对数组进行降序排序，分析其时间复杂度与空间复杂度。

3. 优先队列应用：使用堆实现一个优先队列，并应用其解决任务调度问题，其中每个任务都有优先级，高优先级的任务应当优先执行。

4. 堆构建方法比较：分析并实现自顶向下（top-down）构建堆的方法，比较其与自底向上（bottom-up）方法的时间复杂度差异，并解释为什么自底向上方法更优。

5. 堆排序的稳定性证明：设计一个具体的例子，证明堆排序不是稳定排序算法，即相等元素的相对顺序在排序后可能发生改变。