c语言实现找到数组中前K个最大值并升序输出,利用最小堆实现,将功能拆分成函数形式表达
时间: 2023-06-20 08:05:28 浏览: 51
可以使用最小堆来实现找到数组中前K个最大值,并升序输出的功能。具体实现可以分为以下几个步骤:
1. 建立一个最小堆,堆的大小为K,堆中存放数组中前K个元素。
2. 遍历数组中剩下的元素,如果该元素比堆顶元素大,则将堆顶元素弹出并将该元素加入堆中。
3. 遍历完数组后,堆中存放的就是数组中前K个最大值。
4. 将堆中的元素依次弹出并升序输出即可。
下面是具体的函数实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
// 最小堆结构体
typedef struct {
int *data; // 堆中的数据
int size; // 堆的大小
int capacity; // 堆的容量
} MinHeap;
// 初始化最小堆
MinHeap *initMinHeap(int k) {
MinHeap *heap = (MinHeap *)malloc(sizeof(MinHeap));
heap->data = (int *)malloc(sizeof(int) * k);
heap->size = 0;
heap->capacity = k;
return heap;
}
// 交换两个元素
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 向最小堆中插入元素
void insert(MinHeap *heap, int x) {
if (heap->size == heap->capacity) {
if (x > heap->data[0]) {
heap->data[0] = x;
// 重新构建最小堆
int i = 0, j = 1;
while (j < heap->size) {
if (j + 1 < heap->size && heap->data[j + 1] < heap->data[j]) {
j++;
}
if (heap->data[i] > heap->data[j]) {
swap(&heap->data[i], &heap->data[j]);
i = j;
j = i * 2 + 1;
} else {
break;
}
}
}
} else {
heap->data[heap->size] = x;
int i = heap->size, j = (i - 1) / 2;
while (i > 0 && heap->data[i] < heap->data[j]) {
swap(&heap->data[i], &heap->data[j]);
i = j;
j = (i - 1) / 2;
}
heap->size++;
}
}
// 升序输出最小堆中的元素
void printMinHeap(MinHeap *heap) {
for (int i = 0; i < heap->size; i++) {
printf("%d ", heap->data[i]);
}
}
// 找到数组中前K个最大值
void findTopK(int *nums, int n, int k) {
// 初始化最小堆
MinHeap *heap = initMinHeap(k);
// 将数组中前K个元素加入最小堆
for (int i = 0; i < k; i++) {
insert(heap, nums[i]);
}
// 遍历数组中剩下的元素
for (int i = k; i < n; i++) {
if (nums[i] > heap->data[0]) {
insert(heap, nums[i]);
}
}
// 升序输出最小堆中的元素
printMinHeap(heap);
}
int main() {
int nums[] = {10, 7, 11, 5, 2, 13, 1, 8, 4};
int n = sizeof(nums) / sizeof(nums[0]);
int k = 4;
findTopK(nums, n, k);
return 0;
}
```
以上代码实现了一个利用最小堆找到数组中前K个最大值并升序输出的功能,并将其拆分成了多个函数,便于复用和维护。