C语言找最小K个数编程

在C语言中，找到一组整数中的最小k个数可以采用多种算法实现，其中一种常见的方法是使用优先队列（通常称为堆），特别是大顶堆（Max Heap）。这里提供一个简单的示例，使用大顶堆结构：

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

// 定义一个数组大小
#define MAX_SIZE 100

// 结构体表示堆节点，包含值和索引
typedef struct {
    int value;
    int index;
} MinHeapNode;

// 大顶堆实现，用于存储前k小的元素
void max_heapify(int arr[], int n, int i) {
    int largest = i; // 初始化最大值位置为根节点
    int left = 2 * i + 1; // 左孩子
    int right = 2 * i + 2; // 右孩子
    
    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }
    
    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }
    
    if (largest != i) { // 如果有更大值
        swap(&arr[i], &arr[largest]); // 交换
        max_heapify(arr, n, largest); // 递归调整子树
    }
}

// 建立大顶堆
void build_max_heap(int arr[], int k) {
    for (int i = k / 2 - 1; i >= 0; i--) {
        max_heapify(arr, k, i);
    }
}

// 添加新元素到堆并保持堆性质
void insert(int arr[], int n, int k, int new_val, int new_index) {
    arr[n++] = new_val; // 添加新元素
    max_heapify(arr, k, n - 1); // 调整以保持堆
}

// 获取最小k个数
void get_min_k(int arr[], int k) {
    printf("The smallest %d numbers are:\n", k);
    for (int i = 0; i < k; i++) {
        printf("%d ", arr[0]);
        swap(&arr[0], &arr[k - 1]); // 将当前堆顶移到末尾
        max_heapify(arr, k - 1, 0); // 更新堆
    }
}

// 主函数示例
int main() {
    int arr[] = {9, 8, 7, 6, 5, 4, 3, 2, 1};
    int n = sizeof(arr) / sizeof(arr[0]), k = 3;
    
    build_max_heap(arr, k); // 创建初始堆
    // 假设我们有新元素插入
    insert(arr, n, k, 100, 10); // 新元素：100, 索引：10
    
    get_min_k(arr, k); // 输出前k小数
    return 0;
}

在这个例子中，`build_max_heap()`函数建立了一个大顶堆，`insert()`函数用于添加新元素并维护堆属性，`get_min_k()`函数则从堆中获取并删除最小的k个元素。