堆排序

定义与基本思想

堆排序（Heap Sort）是一种利用堆这种数据结构设计的高效排序算法。其基本思想是：将序列构建成大顶堆（或小顶堆），每次取堆顶元素放到序列末尾，调整剩余元素为新堆，重复直到全部有序。

算法描述

1. 将待排序序列建成大顶堆
2. 取出堆顶元素（最大值），与末尾元素交换，堆长度减 1
3. 调整剩余元素为新大顶堆
4. 重复步骤 2-3，直到堆长度为 1

伪代码如下：

function heapSort(A, n):
    buildMaxHeap(A, n)
    for i = n-1 downto 1:
        swap(A[0], A[i])
        heapify(A, 0, i)

function buildMaxHeap(A, n):
    for i = n/2-1 downto 0:
        heapify(A, i, n)

function heapify(A, i, n):
    largest = i
    l = 2*i+1
    r = 2*i+2
    if l < n and A[l] > A[largest]:
        largest = l
    if r < n and A[r] > A[largest]:
        largest = r
    if largest != i:
        swap(A[i], A[largest])
        heapify(A, largest, n)

堆的定义与性质

• 堆是一棵完全二叉树，用数组存储
• 大顶堆：每个结点的值都大于等于其左右孩子，堆顶是最大值
• 小顶堆：每个结点的值都小于等于其左右孩子，堆顶是最小值
• 结点 i 的左孩子为 2i+1，右孩子为 2i+2，双亲为 $\lfloor (i-1)/2 \rfloor$

代码实现

// 将以 i 为根结点的子树调整为大顶堆
void Heapify(int A[], int i, int n) {
    int largest = i;
    int l = 2 * i + 1, r = 2 * i + 2;
    if (l < n && A[l] > A[largest]) largest = l;
    if (r < n && A[r] > A[largest]) largest = r;
    if (largest != i) {
        int tmp = A[i]; A[i] = A[largest]; A[largest] = tmp;
        Heapify(A, largest, n);  // 递归调整子树
    }
}

// 建堆：从最后一个非叶子结点开始，自底向上调整
void BuildMaxHeap(int A[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        Heapify(A, i, n);
}

// 堆排序
void HeapSort(int A[], int n) {
    BuildMaxHeap(A, n);
    for (int i = n - 1; i > 0; i--) {
        int tmp = A[0]; A[0] = A[i]; A[i] = tmp;  // 堆顶(最大)移到末尾
        Heapify(A, 0, i);                          // 调整剩余部分
    }
}

堆排序与优先队列的关联

堆是优先队列最常用的实现：入队（插入）$O(\log n)$，出队（取最大/最小）$O(\log n)$。Dijkstra 算法、任务调度、Top K 问题等场景都用到了堆。

时间复杂度分析

• 最好/最坏/平均情况：$O(n\log n)$
• 空间复杂度：$O(1)$
• 稳定性：不稳定排序

习题

习题 1

对数组 $A = [4, 10, 3, 5, 1]$ 进行堆排序，写出初始建堆和第一次交换后的堆结构。

习题 2

堆排序的时间复杂度和空间复杂度分别是多少？