C语言最小堆实现（从零开始掌握最小堆数据结构）

什么是堆？

堆是一种基于完全二叉树的数据结构，分为两种：

• 最小堆（Min-Heap）：任意节点的值 ≤ 其子节点的值。
• 最大堆（Max-Heap）：任意节点的值 ≥ 其子节点的值。

本文聚焦于最小堆数据结构，它能快速获取当前集合中的最小元素（时间复杂度 O(1)），非常适合实现优先队列。

为什么用数组表示堆？

由于堆是一棵完全二叉树，我们可以用数组高效地存储它，无需使用指针。对于数组下标从 0 开始的情况：

• 父节点索引：parent(i) = (i - 1) / 2
• 左子节点索引：left(i) = 2 * i + 1
• 右子节点索引：right(i) = 2 * i + 2

C语言最小堆实现步骤

我们将实现以下核心功能：

1. 插入元素（insert）
2. 删除最小元素（extractMin）
3. 上浮（heapifyUp）
4. 下沉（heapifyDown）

1. 定义堆结构

#include <stdio.h>#include <stdlib.h>#include <limits.h>// 堆的最大容量#define MAX_SIZE 100typedef struct {    int data[MAX_SIZE];    int size;} MinHeap;

2. 初始化堆

MinHeap* createMinHeap() {    MinHeap* heap = (MinHeap*)malloc(sizeof(MinHeap));    heap->size = 0;    return heap;}

3. 上浮操作（heapifyUp）

当新元素插入到堆底时，可能破坏堆性质，需将其与父节点比较并上浮。

void heapifyUp(MinHeap* heap, int index) {    if (index == 0) return; // 根节点，无需上浮    int parentIndex = (index - 1) / 2;    if (heap->data[parentIndex] > heap->data[index]) {        // 交换        int temp = heap->data[parentIndex];        heap->data[parentIndex] = heap->data[index];        heap->data[index] = temp;        heapifyUp(heap, parentIndex);    }}

4. 插入元素

void insert(MinHeap* heap, int value) {    if (heap->size >= MAX_SIZE) {        printf("堆已满！\n");        return;    }    heap->data[heap->size] = value;    heap->size++;    heapifyUp(heap, heap->size - 1);}

5. 下沉操作（heapifyDown）

void heapifyDown(MinHeap* heap, int index) {    int left = 2 * index + 1;    int right = 2 * index + 2;    int smallest = index;    if (left < heap->size && heap->data[left] < heap->data[smallest])        smallest = left;    if (right < heap->size && heap->data[right] < heap->data[smallest])        smallest = right;    if (smallest != index) {        int temp = heap->data[index];        heap->data[index] = heap->data[smallest];        heap->data[smallest] = temp;        heapifyDown(heap, smallest);    }}

6. 删除最小元素（根节点）

int extractMin(MinHeap* heap) {    if (heap->size <= 0) {        printf("堆为空！\n");        return INT_MAX;    }    int min = heap->data[0];    heap->data[0] = heap->data[heap->size - 1];    heap->size--;    heapifyDown(heap, 0);    return min;}

完整测试代码

int main() {    MinHeap* heap = createMinHeap();    insert(heap, 10);    insert(heap, 5);    insert(heap, 20);    insert(heap, 3);    insert(heap, 8);    printf("依次取出最小元素：\n");    while (heap->size > 0) {        printf("%d ", extractMin(heap));    }    printf("\n");    free(heap);    return 0;}

运行结果：

依次取出最小元素：3 5 8 10 20

总结

通过本文，你已经掌握了如何用C语言堆操作来构建一个最小堆。这种结构是理解更高级算法（如 Dijkstra 最短路径、堆排序等）的基础。希望这篇教程能帮助你打下坚实的堆排序基础！

如果你觉得有帮助，不妨动手敲一遍代码，加深理解。编程之路，贵在实践！