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

什么是最大堆？

最大堆满足以下性质：

• 它是一棵完全二叉树（所有层都被填满，除了最后一层，且最后一层靠左对齐）。
• 任意节点的值 ≥ 其子节点的值。

在数组中，我们可以用如下方式表示堆：

• 根节点在索引 0。
• 对于任意节点 i：
• 左子节点索引 = 2*i + 1
• 右子节点索引 = 2*i + 2
• 父节点索引 = (i - 1) / 2

C语言最大堆实现步骤

我们将实现以下功能：

1. 初始化堆
2. 插入元素
3. 删除最大元素（堆顶）
4. 堆化（heapify）操作

1. 定义堆结构

#include <stdio.h>#include <stdlib.h>#define MAX_SIZE 100typedef struct {    int data[MAX_SIZE];    int size;} MaxHeap;

2. 初始化堆

void initHeap(MaxHeap* heap) {    heap->size = 0;}

3. 插入元素（上滤）

插入新元素后，可能破坏堆性质，需要“上滤”（sift up）调整。

void insert(MaxHeap* heap, int value) {    if (heap->size == MAX_SIZE) {        printf("堆已满！\n");        return;    }        // 插入到末尾    heap->data[heap->size] = value;    int index = heap->size;    heap->size++;        // 上滤：与父节点比较并交换    while (index > 0) {        int parent = (index - 1) / 2;        if (heap->data[index] >= heap->data[parent]) {            // 交换            int temp = heap->data[index];            heap->data[index] = heap->data[parent];            heap->data[parent] = temp;            index = parent;        } else {            break;        }    }}

4. 删除最大元素（下滤）

删除堆顶（最大值）后，将最后一个元素移到顶部，并“下滤”（sift down）恢复堆性质。

int extractMax(MaxHeap* heap) {    if (heap->size == 0) {        printf("堆为空！\n");        return -1;    }        int max = heap->data[0];    heap->data[0] = heap->data[heap->size - 1];    heap->size--;        // 下滤    int index = 0;    while (1) {        int left = 2 * index + 1;        int right = 2 * index + 2;        int largest = index;                if (left < heap->size && heap->data[left] > heap->data[largest])            largest = left;        if (right < heap->size && heap->data[right] > heap->data[largest])            largest = right;                    if (largest != index) {            int temp = heap->data[index];            heap->data[index] = heap->data[largest];            heap->data[largest] = temp;            index = largest;        } else {            break;        }    }        return max;}

5. 打印堆（用于调试）

void printHeap(MaxHeap* heap) {    for (int i = 0; i < heap->size; i++) {        printf("%d ", heap->data[i]);    }    printf("\n");}

6. 主函数测试

int main() {    MaxHeap heap;    initHeap(&heap);        insert(&heap, 10);    insert(&heap, 20);    insert(&heap, 15);    insert(&heap, 30);    insert(&heap, 40);        printf("堆内容: ");    printHeap(&heap); // 输出应为：40 30 15 10 20（不一定顺序完全一致，但满足堆性质）        printf("最大值: %d\n", extractMax(&heap)); // 输出：40    printf("删除后堆: ");    printHeap(&heap); // 堆重新调整        return 0;}

总结

通过本教程，你已经学会了如何用C语言实现一个完整的最大堆，包括C语言最大堆实现、最大堆数据结构的基本操作、以及C语言堆排序的核心思想。掌握堆的插入与删除机制后，你可以进一步学习堆排序、优先队列等高级算法。

动手实践是掌握编程的关键！建议你复制上面的代码，在本地编译运行，修改参数观察结果，加深理解。