C 语言实现堆排序

堆排序概述

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。在 C 语言实现堆排序的过程中，我们主要会用到最大堆（父节点的值大于子节点的值）来完成排序。

堆的基本概念

1. 完全二叉树：如果一棵二叉树除最后一层外的每一层结点数都达到最大值，且最后一层的结点都集中在该层最左边的若干位置上，那么我们称这棵二叉树为完全二叉树。在堆排序中，我们将待排序的数组看作是一棵完全二叉树。例如，数组 [16, 14, 10, 8, 7, 9, 3, 2, 4, 1] 可以被映射为一棵完全二叉树。
2. 最大堆：最大堆是一种特殊的完全二叉树，它满足每个节点的值都大于或等于其左右子节点的值。最大堆的根节点是堆中的最大值。对于一个数组 arr 表示的完全二叉树，若 arr[i] 是父节点，那么其左子节点为 arr[2 * i + 1]，右子节点为 arr[2 * i + 2]。例如，对于最大堆 [16, 14, 10, 8, 7, 9, 3, 2, 4, 1]，根节点 16 大于它的左子节点 14 和右子节点 10。

堆排序的基本思想

1. 构建最大堆：将初始的数组构建成一个最大堆。这一步是堆排序的关键，通过对数组进行一系列的调整操作，使得数组满足最大堆的性质。具体来说，我们从数组的中间位置开始，依次对每个节点进行调整，使其成为最大堆的一部分。例如，对于数组 [4, 1, 3, 2, 16, 9, 10, 14, 8, 7]，首先从节点 3（索引为 2）开始调整，然后是节点 1（索引为 1），最后是根节点 4（索引为 0）。
2. 排序过程：在构建好最大堆后，堆顶元素（即数组的第一个元素）就是数组中的最大值。我们将堆顶元素与数组的最后一个元素交换位置，此时数组的最后一个元素就是最大值。然后，我们将剩余的 n - 1 个元素重新调整为最大堆，再次将堆顶元素与剩余数组的最后一个元素交换位置。重复这个过程，直到整个数组有序。例如，在第一次交换后，数组变为 [7, 1, 3, 2, 4, 9, 10, 14, 8, 16]，然后对前 9 个元素重新构建最大堆，再交换堆顶和第 9 个元素，依次类推。

C 语言实现堆排序的代码示例

#include <stdio.h>

// 交换两个元素的函数
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 调整堆的函数，使以 i 为根节点的子树成为最大堆
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) {
        swap(&arr[i], &arr[largest]);

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

// 堆排序函数
void heapSort(int arr[], int n) {
    // 构建最大堆
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 一个一个地从堆顶取出元素
    for (int i = n - 1; i > 0; i--) {
        // 将当前堆顶元素移到数组末尾
        swap(&arr[0], &arr[i]);

        // 调用 heapify 函数对剩余的元素进行调整
        heapify(arr, i, 0);
    }
}

// 打印数组的函数
void printArray(int arr[], int n) {
    for (int i = 0; i < n; ++i)
        printf("%d ", arr[i]);
    printf("\n");
}

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

    printf("排序前的数组: \n");
    printArray(arr, n);

    heapSort(arr, n);

    printf("排序后的数组: \n");
    printArray(arr, n);

    return 0;
}

代码解析

1. swap 函数：该函数用于交换两个整数的位置。它接受两个整数指针作为参数，通过一个临时变量 temp 来完成交换操作。例如，如果 a 指向 5，b 指向 3，调用 swap(a, b) 后，a 将指向 3，b 将指向 5。
2. heapify 函数：
   • 参数：arr 是待调整的数组，n 是数组的大小，i 是当前需要调整的节点索引。
   • 过程：首先初始化 largest 为当前节点 i，然后计算其左子节点 left = 2 * i + 1 和右子节点 right = 2 * i + 2。如果左子节点存在且大于当前最大元素 arr[largest]，则更新 largest 为左子节点的索引。同样，如果右子节点存在且大于当前最大元素，也更新 largest。如果 largest 不等于 i，说明当前节点不是最大元素，需要交换 arr[i] 和 arr[largest]，然后递归调用 heapify 函数对受影响的子树进行调整。例如，对于数组 [4, 1, 3]，当 i = 0 时，左子节点 1 小于右子节点 3，所以 largest 更新为 2，然后交换 arr[0] 和 arr[2]，数组变为 [3, 1, 4]，接着对索引为 2 的子树（此时只有一个节点）进行调整，由于没有子节点，调整结束。
3. heapSort 函数：
   • 构建最大堆：通过 for 循环从数组的中间位置 n / 2 - 1 开始，依次对每个节点调用 heapify 函数，将数组构建成最大堆。这是因为从 n / 2 - 1 到 0 的节点是有子节点的节点，需要对它们进行调整以满足最大堆性质。例如，对于数组 [4, 1, 3, 2]，n = 4，n / 2 - 1 = 1，首先对索引为 1 的节点（值为 1）进行 heapify 操作，然后对索引为 0 的节点（值为 4）进行 heapify 操作。
   • 排序过程：通过 for 循环从数组的末尾开始，每次将堆顶元素（即 arr[0]）与当前未排序部分的最后一个元素交换位置，然后对剩余的 i - 1 个元素调用 heapify 函数，重新构建最大堆。例如，对于已经构建好的最大堆 [4, 3, 2, 1]，第一次交换后数组变为 [1, 3, 2, 4]，然后对前 3 个元素 [1, 3, 2] 重新构建最大堆，变为 [3, 1, 2]，再次交换堆顶和最后一个元素，数组变为 [2, 1, 3]，继续对前 2 个元素构建最大堆，直到整个数组有序。
4. printArray 函数：该函数用于打印数组的所有元素。它通过一个 for 循环遍历数组，并使用 printf 函数输出每个元素，元素之间用空格分隔。例如，对于数组 [1, 2, 3]，它将输出 1 2 3。
5. main 函数：在 main 函数中，定义了一个数组 arr 并初始化了一些值，计算了数组的大小 n。首先调用 printArray 函数输出排序前的数组，然后调用 heapSort 函数对数组进行排序，最后再次调用 printArray 函数输出排序后的数组。

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

1. 时间复杂度：
   • 构建最大堆：构建最大堆的时间复杂度为 (O(n))。在构建最大堆的过程中，我们从数组的中间位置开始对每个节点进行 heapify 操作。对于深度为 (h) 的节点，heapify 操作的时间复杂度为 (O(h))。在完全二叉树中，深度为 (h) 的节点数量约为 (2^{h})。通过对所有节点的时间复杂度求和，可以得出构建最大堆的时间复杂度为 (O(n))。例如，对于一个有 (n = 8) 个元素的数组，构建最大堆时，深度为 2 的节点有 4 个，深度为 1 的节点有 2 个，深度为 0 的节点有 1 个，计算总时间复杂度时，(4 \times O(2) + 2 \times O(1) + 1 \times O(0))，最终结果为 (O(n))。
   • 排序过程：在排序过程中，每次交换堆顶元素和未排序部分的最后一个元素后，都需要对剩余的 (n - 1, n - 2, \cdots, 1) 个元素进行 heapify 操作。每次 heapify 操作的时间复杂度为 (O(\log n))，总共进行 (n - 1) 次交换和 heapify 操作，所以排序过程的时间复杂度为 (O(n \log n))。例如，对于一个有 (n = 8) 个元素的数组，第一次交换后对 7 个元素进行 heapify，第二次交换后对 6 个元素进行 heapify，依次类推，由于 heapify 操作的时间复杂度与树的高度有关，而完全二叉树的高度为 (\log n)，所以这部分时间复杂度为 (O(n \log n))。
   • 总体时间复杂度：综合构建最大堆和排序过程，堆排序的时间复杂度为 (O(n \log n))。
2. 空间复杂度：堆排序是一种原地排序算法，除了输入数组本身，它只需要常数级别的额外空间来进行交换和其他临时操作。因此，堆排序的空间复杂度为 (O(1))。

堆排序的应用场景

1. 优先队列：堆排序的思想可以用于实现优先队列。在优先队列中，元素按照优先级进行排序，最大堆可以实现最大优先队列（每次取出优先级最高的元素），最小堆可以实现最小优先队列（每次取出优先级最低的元素）。例如，在操作系统的任务调度中，任务可以按照优先级放入优先队列，调度程序每次从优先队列中取出优先级最高的任务进行执行。
2. 外部排序：当待排序的数据量非常大，无法一次性全部加载到内存中时，可以使用堆排序的思想进行外部排序。将数据分成若干块，在内存中对每一块数据进行堆排序，然后将排序后的块合并起来。例如，在处理大规模日志文件时，可以将日志文件分成多个小文件，在内存中对每个小文件进行堆排序，最后将排序后的小文件合并成一个有序的大文件。
3. 选择问题：在寻找数组中的第 (k) 大（或第 (k) 小）元素时，可以使用堆排序的思想。构建一个大小为 (k) 的最大堆（或最小堆），然后遍历数组，当数组元素大于（或小于）堆顶元素时，将堆顶元素替换为该数组元素，并重新调整堆。遍历结束后，堆顶元素就是第 (k) 大（或第 (k) 小）元素。例如，在一个有 100 个学生成绩的数组中，要找出成绩排名第 10 的学生成绩，可以构建一个大小为 10 的最小堆，遍历数组更新堆，最后堆顶元素就是第 10 名的成绩。

总结堆排序在 C 语言中的实现要点

1. 理解堆的概念：要深入理解完全二叉树和最大堆（或最小堆）的概念，以及它们在数组中的表示方式。这是实现堆排序的基础，只有清楚地知道堆的结构和性质，才能正确地编写 heapify 等函数。
2. heapify 函数的实现：heapify 函数是堆排序的核心函数之一，它负责将以某个节点为根的子树调整为最大堆。在实现过程中，要正确计算子节点的索引，比较节点值的大小，并进行必要的交换和递归操作。
3. 构建最大堆和排序过程：构建最大堆是从数组中间位置开始对每个节点调用 heapify 函数。排序过程则是通过不断交换堆顶元素和未排序部分的最后一个元素，并对剩余元素重新构建最大堆来完成。要注意循环的边界条件和每次操作对数组状态的影响。
4. 时间和空间复杂度分析：了解堆排序的时间复杂度 (O(n \log n)) 和空间复杂度 (O(1))，有助于在实际应用中评估算法的性能和资源需求，从而决定是否选择堆排序算法。

通过以上对 C 语言实现堆排序的详细介绍，希望读者能够深入理解堆排序的原理和实现细节，并在实际编程中能够灵活运用堆排序算法解决相关问题。同时，也可以进一步研究堆排序与其他排序算法（如快速排序、归并排序等）的优缺点和适用场景，以便在不同情况下选择最合适的排序算法。