每日一题——小根堆实现堆排序算法

堆排序的基本思想

堆排序的核心思想是利用小根堆的性质，将数组构建成一个小根堆，然后逐步删除堆顶元素（最小值），并将其放到数组的末尾。通过重复这个过程，数组最终会被排序。

堆排序的步骤

1. 构建小根堆：将数组构建成一个小根堆。
2. 删除最小元素：每次删除堆顶元素（最小值），并将堆的最后一个元素移到堆顶，然后调整堆以保持小根堆的性质。
3. 重复步骤2：直到堆为空，此时数组已经被排序。

实现步骤

1. 构建小根堆

从最后一个非叶子节点开始，逐个向下调整，直到根节点。最后一个非叶子节点的索引为 $ \left\lfloor \frac{2n - 2}{2} \right\rfloor $，其中 $n$ 是数组的长度。

2. 删除最小元素并调整堆

每次删除堆顶元素，将其放到数组的末尾，然后将堆的最后一个元素移到堆顶，再进行向下调整。

C语言实现

#include <stdio.h>
#include <stdlib.h>

// 向下调整堆
void percolateDown(int* arr, int n, int i) {
    int smallest = i; // 当前节点索引
    int left = 2 * i + 1; // 左子节点索引
    int right = 2 * i + 2; // 右子节点索引
	//找到父子结点中的最小节点索引
    // 如果左子节点存在且小于当前节点的值
    if (left < n && arr[left] < arr[smallest]) 
        smallest = left;
        
    // 如果右子节点存在且小于当前最小值
    if (right < n && arr[right] < arr[smallest])
        smallest = right;
    

    // 如果最小值不是当前节点，交换并继续调整堆
    if (smallest != i) {
        int temp = arr[i];
        arr[i] = arr[smallest];
        arr[smallest] = temp;
        percolateDown(arr, n, smallest);  // 递归调整
    }
}

// 构建小根堆
void buildMinHeap(int* arr, int n) {
    // 从最后一个**非叶子节点**开始调整后一大半都是叶子节点
    for (int i = (n - 2) / 2; i >= 0; i--) {
        percolateDown(arr, n, i);
    }
}

// 堆排序
void heapSort(int* arr, int n) {
    // 构建小根堆
    buildMinHeap(arr, n);

    // 逐个删除最小元素并调整堆
    for (int i = n - 1; i >= 0; i--) {
        // 将堆顶元素（最小值）放到数组末尾
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;

        // 调整剩余的堆
        percolateDown(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[] = {3, 1, 6, 5, 2, 4}; // 待排序数组
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, n);

    heapSort(arr, n);  // 执行堆排序

    printf("Sorted array: ");
    printArray(arr, n);  // 输出排序后的数组

    return 0;
}

输出示例

运行上述代码，输出如下：

Original array: 3 1 6 5 2 4 
Sorted array: 1 2 3 4 5 6 

代码解释

1. percolateDown 函数

这个函数用于向下调整堆，确保当前节点的值小于其子节点的值。通过比较当前节点、左子节点和右子节点的值，找到最小值的索引。如果最小值不是当前节点，交换它们，并递归调整子树。

2. buildMinHeap 函数

从最后一个非叶子节点开始，逐个向下调整，直到根节点。最后一个非叶子节点的索引为 $\lfloor \frac{2n-2}{2}\rfloor$。

3. heapSort 函数

首先调用 buildMinHeap 构建小根堆。然后逐个删除堆顶元素（最小值），将其放到数组末尾。每次删除后，调整剩余的堆，确保堆的性质仍然成立。

4. printArray函数

该函数用于打印数组，方便查看排序结果。

排序过程详解

假设我们有一个数组 arr[] = {3, 1, 6, 5, 2, 4}，以下是堆排序的详细过程：

步骤1：构建小根堆

1. 构建小根堆：从最后一个非叶子节点开始向下调整，直到根节点。
   • arr[] = {3, 1, 6, 5, 2, 4}
   • 从索引 2（值为 6）开始：
     • 左子节点 5，右子节点 4，最小值为 4，交换 6 和 4，调整得到 arr[] = {3, 1, 4, 5, 2, 6}。
   • 继续调整索引 1（值为 1）：
     • 左子节点 5，右子节点 2，最小值为 2，交换 1 和 2，调整得到 arr[] = {3, 2, 4, 5, 1, 6}。
   • 最后调整索引 0（值为 3）：
     • 左子节点 2，右子节点 4，最小值为 2，交换 3 和 2，调整得到 arr[] = {2, 3, 4, 5, 1, 6}。
     • 接着，索引 1 的值为 3，继续向下调整，最终得到 arr[] = {2, 1, 4, 5, 3, 6}。

此时，堆构建完成。

步骤2：删除堆顶元素并调整堆

2. 删除堆顶元素并调整堆：
   • 第一次：
     • 删除堆顶元素 2，将堆顶替换为堆的最后一个元素 6，得到 arr[] = {6, 1, 4, 5, 3}。
     • 调整堆，交换 6 和 1，然后交换 6 和 3，得到 arr[] = {1, 3, 4, 5, 6}。
   • 第二次：
     • 删除堆顶元素 1，将堆顶替换为堆的最后一个元素 6，得到 arr[] = {6, 3, 4, 5}。
     • 调整堆，交换 6 和 3，得到 arr[] = {3, 6, 4, 5}，然后交换 6 和 5，得到 arr[] = {3, 5, 4, 6}。
   • 第三次：
     • 删除堆顶元素 3，将堆顶替换为堆的最后一个元素 6，得到 arr[] = {6, 5, 4}。
     • 调整堆，交换 6 和 4，得到 arr[] = {4, 5, 6}。
   • 第四次：
     • 删除堆顶元素 4，将堆顶替换为堆的最后一个元素 6，得到 arr[] = {6, 5}。
     • 调整堆，交换 6 和 5，得到 `arr[] =

{5, 6}`。

• 第五次：
  • 删除堆顶元素 5，将堆顶替换为堆的最后一个元素 6，得到 arr[] = {6}。
  • 此时，堆中只剩一个元素，排序完成。

最终结果

排序后的数组为 arr[] = {1, 2, 3, 4, 5, 6}。

总结

堆排序利用小根堆的性质，通过构建堆、删除堆顶元素并调整堆的方式进行排序。它的时间复杂度为 $O(n\log n)$，空间复杂度为 $O(1)$，是一种原地排序算法，不稳定排序适用于大规模数据的排序任务。