深入理解C语言堆数据结构（从零开始掌握堆的实现与操作）

堆的常见操作

堆支持以下核心操作：

• insert：向堆中插入一个新元素。
• extract：移除并返回堆顶元素（最大值或最小值）。
• heapify：维护堆的性质，通常在插入或删除后调用。

用C语言实现最小堆

下面我们用C语言实现一个简单的最小堆。我们将使用数组来存储堆，并封装几个关键函数。

// min_heap.h#include <stdio.h>#include <stdlib.h>#define MAX_SIZE 100typedef struct {    int data[MAX_SIZE];    int size;} MinHeap;void swap(int *a, int *b) {    int temp = *a;    *a = *b;    *b = temp;}void heapify_up(MinHeap *heap, int index) {    if (index == 0) return;    int parent = (index - 1) / 2;    if (heap->data[index] < heap->data[parent]) {        swap(&heap->data[index], &heap->data[parent]);        heapify_up(heap, parent);    }}void insert(MinHeap *heap, int value) {    if (heap->size >= MAX_SIZE) {        printf("Heap is full!\n");        return;    }    heap->data[heap->size] = value;    heap->size++;    heapify_up(heap, heap->size - 1);}void heapify_down(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) {        swap(&heap->data[index], &heap->data[smallest]);        heapify_down(heap, smallest);    }}int extract_min(MinHeap *heap) {    if (heap->size <= 0) {        printf("Heap is empty!\n");        return -1;    }    int root = heap->data[0];    heap->data[0] = heap->data[heap->size - 1];    heap->size--;    heapify_down(heap, 0);    return root;}

如何使用这个最小堆？

下面是一个简单的测试程序，演示了如何插入元素并提取最小值：

int main() {    MinHeap heap = {0}; // 初始化堆    insert(&heap, 10);    insert(&heap, 5);    insert(&heap, 20);    insert(&heap, 3);    printf("Extracted min: %d\n", extract_min(&heap)); // 输出 3    printf("Extracted min: %d\n", extract_min(&heap)); // 输出 5    return 0;}

总结

通过本教程，你已经掌握了C语言堆数据结构的基本原理和实现方法。无论是最小堆还是最大堆，核心思想都是通过数组模拟完全二叉树，并利用heapify操作维持堆的性质。这种结构在实际开发中应用广泛，比如任务调度、图算法（如Dijkstra）等。

希望这篇关于C语言堆操作的入门教程能帮助你打下坚实的基础！如果你有任何疑问，欢迎在评论区留言交流。