行业网站设计开发费用,科技之门,免费写作文网站,做菠菜网站有没有被骗的1. 理解问题 我们需要设计一个程序#xff0c;读取 80,000 个无序的整数#xff0c;并将它们存储在顺序表#xff08;数组#xff09;中。然后从这些整数中选出最大的前 10 个整数#xff0c;并打印它们。要求我们使用时间复杂度最低的算法。 由于数据量很大#xff0c;直…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. 制定策略
建堆我们通过一个大小为 10 的最小堆来存储当前最大的 10 个数。遍历输入每读取一个数检查该数是否大于堆顶元素如果大于则替换堆顶并调整堆。输出结果遍历完所有数后堆中将包含最大的 10 个数。时间复杂度由于堆的操作是 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 个数。这种方法比直接排序更高效尤其是当数据量很大时。
