C++ 实现堆排序 - 摩柯技术社区

堆排序简介

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

在堆排序中，我们主要利用最大堆（大顶堆）或最小堆（小顶堆）来实现排序。最大堆的特点是每个节点的值都大于或等于其子节点的值，最小堆则相反，每个节点的值都小于或等于其子节点的值。

堆的基本操作

1. 调整堆（heapify）

调整堆是堆排序中的核心操作，它的作用是将一个不符合堆性质的完全二叉树调整为符合堆性质的堆。假设我们要构建一个最大堆，对于给定的数组 arr 和数组的长度 n，以及要调整的节点 i，heapify 操作的实现如下：

void heapify(int arr[], int n, int i) {
    int largest = i; // 初始化最大元素为根节点
    int left = 2 * i + 1; // 左子节点索引
    int right = 2 * i + 2; // 右子节点索引

    // 如果左子节点比根节点大
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // 如果右子节点比最大元素大
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // 如果最大元素不是根节点
    if (largest != i) {
        std::swap(arr[i], arr[largest]);

        // 递归调整受影响的子树
        heapify(arr, n, largest);
    }
}

在上述代码中，首先假设根节点 i 是最大的元素，然后比较左子节点和右子节点与根节点的大小，如果左子节点或右子节点更大，则更新 largest。如果 largest 不等于 i，说明需要交换根节点和最大的子节点，并且递归地对交换后的子树进行 heapify 操作，以确保整个子树都满足堆的性质。

2. 构建堆（buildHeap）

构建堆的过程就是将一个无序数组转换为一个堆。我们可以从数组的中间位置开始，从后往前对每个节点调用 heapify 操作，因为从中间位置开始往后的节点都是叶子节点，叶子节点本身就满足堆的性质，所以不需要对叶子节点进行 heapify。

void buildHeap(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
}

上述代码中，n / 2 - 1 是最后一个非叶子节点的索引。通过从后往前对每个非叶子节点调用 heapify 操作，逐步将整个数组构建成一个堆。

堆排序的实现

有了 heapify 和 buildHeap 操作之后，堆排序的实现就相对简单了。首先，我们将数组构建成一个最大堆，然后将堆顶元素（即最大元素）与数组的最后一个元素交换，此时数组的最后一个位置就是最大元素，然后对剩下的 n - 1 个元素重新调整堆，重复这个过程，直到整个数组有序。

void heapSort(int arr[], int n) {
    buildHeap(arr, n);

    for (int i = n - 1; i > 0; i--) {
        // 将当前堆顶元素移到数组末尾
        std::swap(arr[0], arr[i]);

        // 对剩下的 i 个元素重新调整堆
        heapify(arr, i, 0);
    }
}

在 heapSort 函数中，首先调用 buildHeap 构建最大堆。然后，通过一个循环，每次将堆顶元素（最大元素）与数组末尾元素交换，然后对剩下的元素调用 heapify 操作，将剩下的元素重新调整为最大堆。这个过程不断重复，最终数组就会按升序排列。

完整代码示例

#include <iostream>
#include <algorithm>

// 调整堆
void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest])
        largest = left;

    if (right < n && arr[right] > arr[largest])
        largest = right;

    if (largest != i) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

// 构建堆
void buildHeap(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
}

// 堆排序
void heapSort(int arr[], int n) {
    buildHeap(arr, n);

    for (int i = n - 1; i > 0; i--) {
        std::swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

// 打印数组
void printArray(int arr[], int n) {
    for (int i = 0; i < n; ++i)
        std::cout << arr[i] << " ";
    std::cout << std::endl;
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    std::cout << "Original array: ";
    printArray(arr, n);

    heapSort(arr, n);

    std::cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}

在上述完整代码中，我们定义了 heapify、buildHeap 和 heapSort 函数来实现堆排序的核心逻辑。printArray 函数用于打印数组，main 函数中定义了一个测试数组，并调用 heapSort 函数对其进行排序，最后打印出排序前后的数组。

堆排序的时间复杂度和空间复杂度

1. 时间复杂度

堆排序的时间复杂度主要由构建堆和调整堆的操作决定。

构建堆：构建堆的过程中，每个非叶子节点最多进行一次 heapify 操作。heapify 操作的时间复杂度与树的高度有关，对于一个具有 n 个节点的完全二叉树，树的高度为 log₂n。从最后一个非叶子节点到根节点，每个节点 i 的 heapify 操作时间复杂度为 O(logi)，所以构建堆的时间复杂度为 O(n)。具体推导如下：假设 n 个节点的完全二叉树，其高度为 h = log₂n。构建堆从 n/2 - 1 到 0 对每个非叶子节点调用 heapify。对于高度为 h 的树，第 k 层的节点数最多为 2^k 个，这些节点调用 heapify 的时间复杂度为 O(h - k)。对所有层求和： [ \begin{align*} &\sum_{k = 0}^{h - 1}2^k \cdot O(h - k)\ =&O\left(\sum_{k = 0}^{h - 1}2^k \cdot (h - k)\right)\ =&O\left(h\sum_{k = 0}^{h - 1}2^k-\sum_{k = 0}^{h - 1}k\cdot2^k\right) \end{align*} ] 已知等比数列求和公式 (\sum_{k = 0}^{h - 1}2^k = 2^h - 1)，且 (\sum_{k = 0}^{h - 1}k\cdot2^k=(h - 2)2^h + 2)，又因为 (h = log₂n)，(2^h = n)，代入可得构建堆的时间复杂度为 (O(n))。
调整堆：在堆排序的过程中，每次交换堆顶元素和数组末尾元素后，需要对剩下的 n - 1，n - 2，...，1 个元素进行 heapify 操作。每次 heapify 的时间复杂度为 O(logn)，共进行 n - 1 次，所以这部分的时间复杂度为 O(nlogn)。

综合来看，堆排序的总体时间复杂度为 O(nlogn)，这是一个比较高效的排序算法，无论是在最好、平均还是最坏情况下，时间复杂度都是 O(nlogn)。

2. 空间复杂度

堆排序是一种原地排序算法，除了输入数组本身，它只需要一个常数级别的额外空间来进行交换操作等，所以空间复杂度为 O(1)。

堆排序的应用场景

优先队列：堆排序的思想可以直接应用于实现优先队列。优先队列是一种数据结构，其中每个元素都有一个优先级，优先级高的元素在队列前面。在 C++ 标准库中，std::priority_queue 就是基于堆实现的。在很多场景中，比如任务调度系统，我们需要根据任务的优先级来安排任务的执行顺序，这时就可以使用优先队列。例如，在一个多线程的服务器程序中，不同的请求可能有不同的优先级，高优先级的请求需要优先处理，我们可以将这些请求放入一个优先队列（基于堆实现），然后按照优先级顺序取出并处理。
外部排序：当数据量非常大，无法一次性加载到内存中时，堆排序可以用于外部排序。在外部排序中，我们可以将数据分成多个小的部分，在内存中对每个小部分进行排序（例如使用堆排序），然后将这些有序的小部分合并起来。堆排序在这个过程中可以有效地对每个小部分进行排序，并且由于其时间复杂度稳定，在处理大量数据时表现良好。
寻找第 K 大（小）的元素：通过构建一个大小为 K 的堆（最大堆找第 K 小，最小堆找第 K 大），遍历数组，将元素与堆顶元素比较并调整堆，最终堆顶元素就是第 K 大（小）的元素。例如，在一个成绩排名系统中，我们可能只关心前 10 名的学生成绩，就可以使用这种方法快速找到。

与其他排序算法的比较

与冒泡排序、选择排序、插入排序的比较：冒泡排序、选择排序和插入排序的时间复杂度在最坏和平均情况下都是 O(n²)，而堆排序的时间复杂度稳定在 O(nlogn)。这意味着当数据规模 n 较大时，堆排序的效率要远远高于这三种简单排序算法。例如，对于一个包含 10000 个元素的数组，简单排序算法可能需要执行数百万次甚至更多的操作，而堆排序只需要执行几十万次操作。不过，在数据规模较小或者数据已经部分有序的情况下，插入排序可能会比堆排序表现得更好，因为插入排序在这种情况下的时间复杂度可以接近 O(n)。
与快速排序的比较：快速排序的平均时间复杂度也是 O(nlogn)，在大多数情况下，快速排序的性能要优于堆排序，因为快速排序的常数因子较小。然而，快速排序在最坏情况下的时间复杂度会退化为 O(n²)，例如当每次选择的枢轴都是数组中的最大或最小元素时。而堆排序的时间复杂度在任何情况下都稳定在 O(nlogn)。所以，在对稳定性有要求（堆排序是不稳定排序，快速排序可以通过一些方法实现稳定排序）或者对最坏情况时间复杂度有严格要求的场景下，堆排序可能是更好的选择。
与归并排序的比较：归并排序的时间复杂度也是稳定的 O(nlogn)，并且归并排序是稳定排序，而堆排序是不稳定排序。在空间复杂度方面，归并排序需要 O(n) 的额外空间来进行合并操作，而堆排序只需要 O(1) 的额外空间。所以，如果空间有限，堆排序可能更适合；如果对稳定性有要求，归并排序则是更好的选择。

注意事项

堆的性质维护：在实现堆排序的过程中，一定要确保堆的性质始终得到维护。无论是在 heapify 操作还是在交换元素后重新调整堆的过程中，都要仔细检查是否满足最大堆（或最小堆）的性质。如果堆的性质被破坏，整个排序过程将无法得到正确的结果。例如，在 heapify 操作中，如果没有正确比较子节点和父节点的大小，可能会导致部分子树不满足堆的性质，最终影响排序结果。
边界条件处理：在代码实现中，要注意边界条件的处理。比如在 heapify 函数中，要确保左子节点和右子节点的索引不超过数组的边界。在构建堆和进行排序的循环中，也要正确处理数组的索引范围。如果边界条件处理不当，可能会导致数组越界访问，从而引发程序崩溃或未定义行为。例如，在 heapify 中，如果没有检查 left < n 和 right < n，当 left 或 right 超出数组范围时，访问 arr[left] 或 arr[right] 会导致未定义行为。
稳定性：堆排序是一种不稳定的排序算法。这意味着在排序过程中，相等元素的相对顺序可能会发生改变。如果在某些应用场景中，元素的相对顺序很重要，那么就需要考虑使用稳定的排序算法，如归并排序或基数排序。例如，在对学生成绩进行排序时，如果我们希望成绩相同的学生按照原来的报名顺序排列，那么堆排序就不适合，而应该选择稳定排序算法。

通过深入理解堆排序的原理、实现细节、复杂度分析以及与其他排序算法的比较，我们可以在实际编程中根据不同的需求和场景，合理选择使用堆排序或其他更合适的排序算法，从而提高程序的效率和性能。