c语言实现找到数组中前K个最大值并升序输出,利用堆实现
时间: 2023-06-20 17:05:33 浏览: 59
以下是利用堆实现找到数组中前 K 个最大值并升序输出的 C 语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义堆结构体
typedef struct Heap {
int size; // 堆大小
int *arr; // 堆数组指针
} Heap;
// 初始化堆
void initHeap(Heap *heap, int size) {
heap->size = 0;
heap->arr = (int *)malloc(sizeof(int) * size);
}
// 交换堆中两个元素的值
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 向堆中插入元素
void insert(Heap *heap, int val) {
int i;
// 将元素插入到堆的末尾
heap->arr[heap->size] = val;
// 向上调整堆,使其仍然满足堆的性质
i = heap->size;
while (i > 0 && heap->arr[i] > heap->arr[(i - 1) / 2]) {
swap(&heap->arr[i], &heap->arr[(i - 1) / 2]);
i = (i - 1) / 2;
}
heap->size++;
}
// 从堆中删除元素
int removeTop(Heap *heap) {
int i, j, ret;
if (heap->size == 0) {
return -1;
}
// 将堆顶元素保存下来
ret = heap->arr[0];
// 将堆末尾元素放到堆顶
heap->arr[0] = heap->arr[heap->size - 1];
heap->size--;
// 向下调整堆,使其仍然满足堆的性质
i = 0;
while (i * 2 + 1 < heap->size) {
j = i * 2 + 1;
if (j + 1 < heap->size && heap->arr[j] < heap->arr[j + 1]) {
j++;
}
if (heap->arr[i] < heap->arr[j]) {
swap(&heap->arr[i], &heap->arr[j]);
i = j;
} else {
break;
}
}
return ret;
}
// 找到数组中前 K 个最大值并升序输出
void findTopK(int *arr, int n, int k) {
int i;
Heap heap;
// 初始化堆
initHeap(&heap, k);
// 将前 K 个元素插入堆中
for (i = 0; i < k; i++) {
insert(&heap, arr[i]);
}
// 遍历剩余元素
for (i = k; i < n; i++) {
// 如果当前元素大于堆顶元素,则将其插入堆中,并删除堆顶元素
if (arr[i] > heap.arr[0]) {
removeTop(&heap);
insert(&heap, arr[i]);
}
}
// 输出堆中元素
for (i = 0; i < k; i++) {
printf("%d ", removeTop(&heap));
}
printf("\n");
}
int main() {
int arr[] = {9, 3, 7, 6, 5, 1, 4, 2, 8, 0};
int n = sizeof(arr) / sizeof(int);
int k = 4;
findTopK(arr, n, k);
return 0;
}
```
该代码的主要思路是利用堆来维护前 K 个最大值,遍历数组时,如果当前元素大于堆顶元素,则将其插入堆中,并删除堆顶元素。最后输出堆中元素即可。由于堆的性质,堆中元素是升序排列的。