c语言实现 堆的建立和维护 实践堆结构

建立堆的过程，我们需要先了解什么是堆。堆是一种特殊的树型数据结构，其中每个节点都有一个值，通常我们所说的堆都是指二叉堆，它满足以下两个性质：

1. 父节点的值总是大于或等于（小于或等于）任何一个子节点的值。
2. 每个节点的左子树和右子树都是一个堆。

堆分为最大堆和最小堆，根据它们的性质可以快速找到最大或最小值。以下是用 C 语言实现最大堆的代码：

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

#define MAX_SIZE 100

int heap[MAX_SIZE];
int size = 0;

// 交换两个元素的位置
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 向上调整堆
void sift_up(int i) {
    while (i > 0 && heap[i] > heap[(i - 1) / 2]) {
        swap(&heap[i], &heap[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

// 向下调整堆
void sift_down(int i) {
    int max_index = i;
    int left = i * 2 + 1;
    int right = i * 2 + 2;

    if (left < size && heap[left] > heap[max_index]) {
        max_index = left;
    }

    if (right < size && heap[right] > heap[max_index]) {
        max_index = right;
    }

    if (i != max_index) {
        swap(&heap[i], &heap[max_index]);
        sift_down(max_index);
    }
}

// 插入元素
void insert(int x) {
    if (size == MAX_SIZE) {
        printf("Heap is full.\n");
        return;
    }

    heap[size] = x;
    size++;
    sift_up(size - 1);
}

// 删除堆顶元素
int pop() {
    if (size == 0) {
        printf("Heap is empty.\n");
        return -1;
    }

    int root = heap[0];
    heap[0] = heap[size - 1];
    size--;
    sift_down(0);
    return root;
}

int main() {
    insert(3);
    insert(2);
    insert(1);
    printf("%d\n", pop()); // 输出 3
    printf("%d\n", pop()); // 输出 2
    printf("%d\n", pop()); // 输出 1
    printf("%d\n", pop()); // 输出 Heap is empty.
    return 0;
}

这个实现中，我们使用了一个数组来存储堆的元素，使用一个变量 `size` 来表示堆的大小，插入元素时先将元素放到数组最后，然后向上调整堆，删除堆顶元素时将最后一个元素放到堆顶，然后向下调整堆。这个实现中，我们使用了递归来向下调整堆，也可以使用循环来实现。