堆排序

定义

堆排序（Heap Sort）是一种基于完全二叉树的选择排序算法。它利用堆这种数据结构来进行排序，是简单选择排序的改进版本。

堆的定义

• 大根堆（大顶堆）：每个结点的值都 $\geq$ 其左右孩子结点的值，即 $L(i) \geq L(2i)$ 且 $L(i) \geq L(2i+1)$，堆顶是最大值
• 小根堆（小顶堆）：每个结点的值都 $\leq$ 其左右孩子结点的值，即 $L(i) \leq L(2i)$ 且 $L(i) \leq L(2i+1)$，堆顶是最小值

核心思想

1. 将待排序序列构建成一个大根堆（建堆过程）
2. 将堆顶元素（最大值）与堆底元素交换，最大值到达最终位置
3. 将剩余 $n-1$ 个元素重新调整为堆
4. 重复步骤 2-3，直到堆中只剩一个元素

基于大根堆的堆排序得到递增序列，基于小根堆得到递减序列。

关键特性

• 堆是层序存储的完全二叉树，用数组实现
• 编号为 $i$ 的结点：左孩子 $= 2i$，右孩子 $= 2i+1$，父结点 $= \lfloor i/2\rfloor$
• 堆排序是不稳定的
• 时间复杂度始终为 $O(n\log_2 n)$，与初始序列无关
• 建堆时间复杂度为 $O(n)$，调整堆时间复杂度为 $O(\log_2 n)$

建堆过程（以大根堆为例）

1. 将序列按层序存储为完全二叉树
2. 从最后一个非叶子结点开始（编号为 $\lfloor n/2\rfloor$），向前依次调整
3. 对每个非叶子结点，检查是否满足大根堆性质：
   • 如果当前结点 $<$ 某个孩子结点，则与较大的孩子交换
   • 交换后继续向下检查，直到满足堆性质
4. 调整完成后，序列构成大根堆

排序过程

1. 将堆顶元素（最大值）与堆的最后一个元素交换
2. 堆的规模减 1（最后一个元素已到达最终位置）
3. 对新的堆顶元素进行向下调整，恢复堆性质
4. 重复步骤 1-3，共执行 $n-1$ 趟

向下调整（Sift Down）

1. 设当前结点为 parent，其左孩子为 $child = 2 \times parent$
2. 如果有右孩子且右孩子 $>$ 左孩子，则 child 指向右孩子
3. 如果 $parent < child$，则交换两者
4. parent 移到 child 位置，继续向下调整
5. 直到 $parent \geq child$（或到达叶子结点）

// 向下调整函数（大根堆）
void SiftDown(int A[], int start, int end) {
    int parent = start;
    int child = 2 * parent + 1;  // 左孩子（数组下标从 0 开始）
    while (child <= end) {
        // 选择较大的孩子
        if (child + 1 <= end && A[child] < A[child + 1])
            child++;
        // 如果父结点 >= 较大的孩子，调整结束
        if (A[parent] >= A[child])
            return;
        else {
            // 交换父子结点
            int temp = A[parent];
            A[parent] = A[child];
            A[child] = temp;
            // 继续向下调整
            parent = child;
            child = 2 * parent + 1;
        }
    }
}

// 建堆 + 堆排序
void HeapSort(int A[], int len) {
    // 第一步：建堆，从最后一个非叶子结点开始
    for (int i = (len - 2) / 2; i >= 0; i--)
        SiftDown(A, i, len - 1);

    // 第二步：排序
    for (int i = len - 1; i > 0; i--) {
        // 将堆顶（最大值）与堆底交换
        int temp = A[0];
        A[0] = A[i];
        A[i] = temp;
        // 对剩余元素重新调整为堆
        SiftDown(A, 0, i - 1);
    }
}