二叉堆

二叉堆（Binary Heap）是一种特殊的堆，它是一棵完全二叉树，并满足堆的性质：对于每个节点x，其父节点的值小于等于x的值（最小堆），或者大于等于x的值（最大堆）。在二叉堆中，根节点存储的是堆中的最小（或最大）元素。

二叉堆通常使用数组来实现。假设根节点在数组中的下标为0，则第i个节点的左子节点在数组中的下标为2i+1，右子节点的下标为2i+2，父节点的下标为floor((i-1)/2)。这种实现方式使得二叉堆的任何操作的时间复杂度均为O(log n)，其中n是堆中元素的数量。

二叉堆的基本操作包括：

• 插入元素：将元素插入到堆中的正确位置，然后对堆进行调整，以满足堆的性质。
• 删除元素：删除堆中的根节点，然后将堆的最后一个元素移动到根节点的位置，并对堆进行调整，以满足堆的性质。
• 查找最小元素：返回堆的根节点。
• 修改元素：将堆中的某个元素的值修改为新值，然后对堆进行调整，以满足堆的性质。

二叉堆的应用场景包括但不限于：

• 堆排序：堆排序使用最大堆（或最小堆）来对数组进行排序。
• 优先级队列：优先级队列使用最小堆（或最大堆）来实现，可以在O(log n)的时间内插入元素和返回队列中的最小（或最大）元素。
• 图论算法：Dijkstra算法和Prim算法使用最小堆来实现。
• 哈夫曼编码：哈夫曼编码使用最小堆来构建Huffman树。
• 模拟系统：二叉堆可以用于模拟系统，其中每个事件都有一个优先级，优先级高的事件会先执行。

以下是二叉堆的C语言实现

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

#define MAX_HEAP_SIZE 100

// 二叉堆结构体
typedef struct binary_heap {
    int* heap;  // 堆的数组
    int size;   // 堆的大小
    int capacity;   // 堆的容量
} BinaryHeap;

// 创建二叉堆
BinaryHeap* createHeap(int capacity) {
    BinaryHeap* heap = (BinaryHeap*)malloc(sizeof(BinaryHeap));
    heap->heap = (int*)malloc(sizeof(int) * capacity);
    heap->size = 0;
    heap->capacity = capacity;
    return heap;
}

// 释放二叉堆
void destroyHeap(BinaryHeap* heap) {
    free(heap->heap);
    free(heap);
}

// 上滤
void siftUp(BinaryHeap* heap, int index) {
    int parent = (index - 1) / 2;
    int temp = heap->heap[index];
    while (index > 0 && heap->heap[parent] > temp) {
        heap->heap[index] = heap->heap[parent];
        index = parent;
        parent = (index - 1) / 2;
    }
    heap->heap[index] = temp;
}

// 下滤
void siftDown(BinaryHeap* heap, int index) {
    int temp = heap->heap[index];
    int child = 2 * index + 1;
    while (child < heap->size) {
        if (child + 1 < heap->size && heap->heap[child + 1] < heap->heap[child]) {
            child++;
        }
        if (heap->heap[child] < temp) {
            heap->heap[index] = heap->heap[child];
            index = child;
            child = 2 * index + 1;
        } else {
            break;
        }
    }
    heap->heap[index] = temp;
}

// 插入元素
void insert(BinaryHeap* heap, int value) {
    if (heap->size == heap->capacity) {
        printf("Heap is full.\n");
        return;
    }
    heap->heap[heap->size] = value;
    siftUp(heap, heap->size);
    heap->size++;
}

// 删除最小元素
void deleteMin(BinaryHeap* heap) {
    if (heap->size == 0) {
        printf("Heap is empty.\n");
        return;
    }
    heap->heap[0] = heap->heap[heap->size - 1];
    heap->size--;
    siftDown(heap, 0);
}

// 打印堆的元素
void printHeap(BinaryHeap* heap) {
    printf("Heap: ");
    for (int i = 0; i < heap->size; i++) {
        printf("%d ", heap->heap[i]);
    }
    printf("\n");
}

// 测试
int main() {
    BinaryHeap* heap = createHeap(MAX_HEAP_SIZE);
    insert(heap, 10);
    insert(heap, 5);
    insert(heap, 20);
    insert(heap, 3);
    printHeap(heap);
    deleteMin(heap);
    printHeap(heap);
    destroyHeap(heap);
    return 0;
}