利用编程思维做题之最小堆选出最大的前10个整数

1. 理解问题

        我们需要设计一个程序，读取 80,000 个无序的整数，并将它们存储在顺序表（数组）中。然后从这些整数中选出最大的前 10 个整数，并打印它们。要求我们使用时间复杂度最低的算法。

        由于数据量很大，直接排序的时间复杂度较高，因此我们需要一个更高效的算法。最小堆 是一种合适的选择，因为它能够在 O(n log k) 的时间复杂度内完成最大 10 个整数的选取。

2. 输入输出

• 输入：通过键盘输入 80,000 个整数。
• 输出：打印出最大的 10 个整数。

3. 数据结构

        我们使用一个最小堆来存储当前最大 10 个数。堆的根节点是堆中最小的元素，插入新元素时，如果新元素大于堆的根节点，则替换根节点并调整堆结构。这样，在遍历完所有 80,000 个数之后，堆中的 10 个元素就是最大的 10 个整数。

        最小堆的数据结构如下：

struct MinHeap {
    int* arr;     // 存储堆的数组
    int size;     // 当前堆的大小
    int capacity; // 堆的最大容量
};

4. 制定策略

1. 建堆：我们通过一个大小为 10 的最小堆来存储当前最大的 10 个数。
2. 遍历输入：每读取一个数，检查该数是否大于堆顶元素，如果大于，则替换堆顶并调整堆。
3. 输出结果：遍历完所有数后，堆中将包含最大的 10 个数。
4. 时间复杂度：由于堆的操作是 O(log k)，每次插入操作的时间复杂度为 O(log 10)，因此整个过程的时间复杂度是 O(n log 10) ≈ O(n)。

5. 实现代码

5.1 完整代码

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

// 最小堆的结构体定义
struct MinHeap {
    int* arr;     // 存储堆的数组
    int size;     // 当前堆的大小，即有数值的个数
    int capacity; // 堆的最大容量
};

// 创建最小堆
struct MinHeap* createMinHeap(int capacity) {
    // 定义一个MinHeap结构体大小的指针，指向一个堆
    struct MinHeap* heap = (struct MinHeap*)malloc(sizeof(struct MinHeap));
    heap->arr = (int*)malloc(sizeof(int) * capacity);
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

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

// 维护堆的性质（向下调整）
void heapify(struct MinHeap* heap, int index) {
    int left = 2 * index + 1;
    int right = 2 * index + 2;
    int smallest = index;

    // 找出最小的元素
    if (left < heap->size && heap->arr[left] < heap->arr[smallest]) {
        smallest = left;
    }
    if (right < heap->size && heap->arr[right] < heap->arr[smallest]) {
        smallest = right;
    }

    // 如果最小元素不是当前元素，交换并继续调整
    if (smallest != index) {
        swap(&heap->arr[index], &heap->arr[smallest]);
        heapify(heap, smallest);
    }
}

// 维护堆的性质（向上调整）
void upheapify(struct MinHeap* heap, int index) {
    while (index > 0 && heap->arr[index] < heap->arr[(index - 1) / 2]) {
        swap(&heap->arr[index], &heap->arr[(index - 1) / 2]);
        index = (index - 1) / 2;
    }
}

// 插入元素到堆中
void insert(struct MinHeap* heap, int value) {
    if (heap->size < heap->capacity) {
        // 如果堆未满，直接插入
        heap->arr[heap->size] = value;
        upheapify(heap, heap->size);  // 插入后需要向上调整
        heap->size++;
    } else if (value > heap->arr[0]) {
        // 如果堆已满且当前值大于堆顶元素，则替换堆顶
        heap->arr[0] = value;
        heapify(heap, 0);  // 替换堆顶后需要进行堆化
    }
}

// 打印堆中的前 10 个最大值
void printTop10(struct MinHeap* heap) {
    // 最小堆中的前 10 个最大值已经存储在堆中，直接打印
    for (int i = 0; i < heap->size; i++) {
        printf("%d ", heap->arr[i]);
    }
    printf("\n");
}

// 主程序
int main() {
    struct MinHeap* heap = createMinHeap(10); // 创建一个容量为 10 的最小堆
    int value;

    printf("请输入 80000 个整数（每输入一个整数后按 Enter，输入 80000 个数）：\n");

    // 读取 80,000 个整数
    for (int i = 0; i < 80000; i++) {
        scanf("%d", &value);
        insert(heap, value); // 将输入的值插入堆中
    }

    // 打印堆中的前 10 个最大值
    printf("最大的 10 个整数是：\n");
    printTop10(heap);

    // 释放堆内存
    free(heap->arr);
    free(heap);

    return 0;
}
 

6. 代码说明

• 结构体定义：我们定义了一个 MinHeap 结构体来表示最小堆，包含一个数组 arr 存储堆的元素，size 表示当前堆的大小，capacity 是堆的最大容量（即 10）。
• 堆的操作：
  • createMinHeap：创建一个新的最小堆。
  • swap：交换堆中的两个元素。
  • heapify：维护堆的性质，确保堆仍然是最小堆。
  • insert：将新元素插入堆。如果堆未满，直接插入。如果堆已满并且新元素大于堆顶元素，则替换堆顶并重新调整堆。
  • printTop10：打印堆中的前 10 个最大值（即堆中的元素）。
• 主程序：
  • 通过 scanf 读取 80,000 个整数，并将它们插入最小堆。
  • 插入操作将保证堆中始终保存着最大的 10 个元素。
  • 最后输出堆中的元素，即为最大的 10 个整数。

7. 模拟过程

假设输入为：

2 5 8 12 20 10 1 35 27 50 41 39 70 80 90 23 17 16 13 11 ...

程序将使用最小堆的结构，维护堆中最大 10 个数。每读取一个新数，程序将插入最小堆，并保证堆的大小不超过 10。当所有 80,000 个数输入完成后，堆中将包含最大的 10 个数。

8. 运行结果

        假设输入的数据中最大的 10 个数为：90, 80, 70, 50, 41, 39, 35, 27, 23, 20，程序输出：

        最大的 10 个整数是：90 80 70 50 41 39 35 27 23 20 

        注意，此代码只会获取最大的10个数，但不会排序这10个数。

9. 时间和空间复杂度分析

• 时间复杂度：
  • 建堆的时间复杂度：每次插入一个元素时，最小堆的插入操作为 O(log 10) = O(1)，因此整个过程的时间复杂度是 O(n)，其中 n 为 80,000。
• 空间复杂度：最小堆需要 O(10) 的空间来存储最大 10 个数，因此空间复杂度为 O(1)，即常数空间。

10. 总结

        通过使用最小堆，我们能够以 O(n) 的时间复杂度找到并输出最大的 10 个数。这种方法比直接排序更高效，尤其是当数据量很大时。