堆排序可视化演示

默认/待处理
比较中/交换中
当前调整根 (Heapify)
已排序

数组视图

二叉堆树视图 (逻辑结构)

准备开始排序演示。点击“开始排序”按钮启动动画，或先“生成新数组”。
状态: 就绪
中等

堆排序算法介绍

核心思想

堆排序（Heap Sort）是一种基于比较的排序算法，它巧妙地利用了“堆”这种数据结构。核心思想是：首先将待排序的序列构建成一个特定类型的堆（通常是最大堆或最小堆），然后依次将堆顶元素（即当前序列中的最大或最小值）取出，放到序列末尾，并调整剩余元素重新构成堆，重复此过程直到所有元素都被取出。

堆的性质与表示

堆是一个近似完全二叉树的结构，并满足堆序性质：

  • 最大堆（Max Heap）：任意节点的值都不小于其子节点的值。根节点是整个堆中的最大值。
  • 最小堆（Min Heap）：任意节点的值都不大于其子节点的值。根节点是整个堆中的最小值。

为了实现升序排序，我们通常使用最大堆。虽然堆是树形结构，但常用数组高效地表示它：

  • 对于数组索引 i 的节点：
  • 左子节点索引：2 * i + 1
  • 右子节点索引：2 * i + 2
  • 父节点索引：floor((i - 1) / 2)
  • （需确保索引在数组范围内）
基本步骤 (使用最大堆实现升序)
  1. 构建最大堆 (Build Max Heap)： 将无序的原始数组调整为一个最大堆。通常从最后一个非叶子节点（索引为 `floor(n/2) - 1`）开始，自底向上、从右到左调用调整堆的函数 (Heapify)。
  2. 排序过程：
    • 将堆顶元素（当前最大值）与堆末尾的元素交换。
    • 此时，序列末尾的元素已就位（已排序）。
    • 将堆的大小减 1（逻辑上排除已排序的末尾元素）。
    • 对新的堆顶元素（原末尾元素）调用调整堆的函数 (Heapify)，使其重新满足最大堆性质。
    • 重复上述交换、缩小堆、调整堆顶的过程，直到堆中只剩一个元素。

最终，数组将变为升序排列。

复杂度分析
复杂度类型 最好情况 平均情况 最坏情况
时间复杂度 O(n log n) O(n log n) O(n log n)
空间复杂度 O(1) O(1) O(1)

解释 O(n log n) 时间复杂度：

  • 建堆 (Build Heap): 虽然看起来涉及多次 `Heapify` (每次 O(log n))，但精确分析表明，构建一个大小为 n 的堆只需要 O(n) 时间。可以理解为：大部分节点都在堆的底层，调整它们的成本很低（接近 O(1)），只有靠近根节点的少数节点需要 O(log n) 的调整。将所有节点的调整成本加起来，总和是线性的 O(n)。
  • 排序阶段: 需要进行 n-1 次“提取最大值并调整堆”的操作。每次提取涉及一次交换 (O(1)) 和一次 `Heapify` (O(log k)，其中 k 是当前堆的大小，k 从 n-1 减小到 1)。总时间约为 Σ(log k) for k=1 to n-1，这仍然是 O(n log n)。

因此，总时间复杂度是 O(n) + O(n log n) = O(n log n)。堆排序的时间复杂度不依赖于输入数据的初始顺序。

空间复杂度 O(1)： 堆排序是**原地排序算法 (in-place)**，因为它主要在原始输入数组上进行操作，只需要常数级别的额外空间用于存储临时变量（如交换元素时）或递归调用栈（如果使用递归 `heapify`，栈深度通常为 O(log n)；迭代实现则为 O(1)），因此空间复杂度为 O(1)。

注意： 对于非常大的数据集，虽然渐进复杂度不变，但实际运行中 DOM 操作（更新可视化）可能会成为性能瓶颈，导致动画变慢。

堆排序代码实现

C++ 实现
// C++ 堆排序实现 (使用最大堆进行升序排序)
#include <iostream> 
#include <vector>
#include <algorithm> // 为了 swap

// 使用 std 命名空间简化代码 (在大型项目中可能不推荐)
using namespace std;

/**
 * @brief 调整子树，使其满足最大堆性质 (Max Heapify)
 * @param arr 存储堆的向量 (vector)
 * @param n 堆的大小 (数组中参与堆操作的元素数量)
 * @param i 需要调整的子树的根节点索引
 */
void heapify(vector& arr, int n, int i) {
    int largest = i;       // 假设当前根节点是最大的
    int left = 2 * i + 1;  // 左子节点索引
    int right = 2 * i + 2; // 右子节点索引

    // 检查左子节点是否存在 (索引 < n) 且值大于当前最大值
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // 检查右子节点是否存在 (索引 < n) 且值大于当前最大值
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // 如果 largest 不再是根节点 i，说明其某个子节点更大，需要调整
    if (largest != i) {
        swap(arr[i], arr[largest]); // 交换根节点与较大的子节点

        // 由于交换可能破坏了下一级子树的最大堆性质,
        // 需要递归地对被交换下去的那个节点 (现在索引为 largest) 所在的子树进行 heapify
        heapify(arr, n, largest);
    }
    // 如果 largest == i, 说明当前节点已经是其子树中最大的，无需操作
}

/**
 * @brief 对给定的向量执行堆排序 (升序)
 * @param arr 待排序的向量 (会被原地修改)
 */
void heapSort(vector& arr) {
    int n = arr.size();
    if (n <= 1) return; // 处理空向量或单元素向量，无需排序

    // 1. 构建最大堆 (Build Max Heap)
    // 从最后一个非叶子节点开始，自底向上，自右向左，对每个节点调用 heapify
    // 最后一个非叶子节点的索引是 floor(n/2) - 1
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
    // 循环结束后，arr[0...n-1] 形成一个最大堆, arr[0] 是最大元素

    // 2. 排序阶段：依次将堆顶元素(最大值)与堆末尾元素交换，并缩小堆的大小
    for (int i = n - 1; i > 0; i--) {
        // 将当前堆顶（即当前未排序部分的最大值 arr[0]）
        // 与当前堆的最后一个元素 (arr[i]) 交换
        swap(arr[0], arr[i]);
        // 交换后，arr[i] 已是最终排序位置，不再参与后续堆操作

        // 逻辑上将堆的大小减 1 (下次 heapify 只考虑 arr[0...i-1])
        // 并对新的根节点 (arr[0], 原来的 arr[i]) 调用 heapify，
        // 以维护 arr[0...i-1] 范围内的最大堆性质
        heapify(arr, i, 0); // 注意，此时堆的大小是 i (不包括已排序的末尾部分)
    }
    // 循环结束后，数组变为升序排列
}

// 主函数，用于测试
int main() {
    vector arr = {12, 11, 13, 5, 6, 7};

    cout << "原始数组: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    heapSort(arr);

    cout << "排序后数组: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}