对二叉堆的简单分析，c和c++的简单实现

   上文：[Redis的实现五：二叉堆的数据结构和TTL、c，c++的实现-CSDN博客](https://blog.csdn.net/m0_63251896/article/details/135691889?spm=1001.2014.3001.5501 "Redis的实现五：二叉堆的数据结构和TTL、c，c++的实现-CSDN博客")

   **概述**：二叉堆是一种基于完全二叉树结构的数据结构，常被用作优先队列的实现方式。它有两种类型：最大堆和最小堆，分别用于支持在堆中的元素中找到最大值或最小值。

以下是二叉堆的一些简单分析：

1. 结构特点：

   • 二叉堆是一颗完全二叉树，这意味着除了最后一层，其他层都是完全填充的，而且最后一层的节点都尽量靠左排列。
   • 在最大堆中，每个节点的值都大于或等于其子节点的值；在最小堆中，每个节点的值都小于或等于其子节点的值。

2. 数组表示：

   • 二叉堆可以使用数组来表示。对于给定索引 i，其左子节点的索引为 2i+1，右子节点的索引为 2i+2，父节点的索引为 (i-1)/2。
   • 这种数组表示使得堆的访问和修改操作更加高效。

3. 堆的操作：

   • 插入：将新元素添加到堆的末尾，然后通过一系列交换操作，使得堆的性质得以保持。
   • 删除：删除堆顶元素后，将堆的最后一个元素移到堆顶，然后通过一系列交换操作，使得堆的性质得以保持。
   • 堆化：通过自上而下的或自下而上的方式，确保堆的性质得以保持。

4. 时间复杂度：

   • 插入和删除操作的时间复杂度为O(log n)，其中n是堆中元素的个数。
   • 构建堆的时间复杂度为O(n)，其中n是堆中元素的个数。

5. 应用：

   • 优先队列：由于能够快速找到最大值或最小值，二叉堆常被用作优先队列的基础数据结构。
   • 堆排序：利用最大堆或最小堆实现的堆排序算法是一种高效的排序算法。

总体而言，二叉堆是一种简单而强大的数据结构，通过有效地维护元素的顺序，它支持高效的插入、删除和查找最值等操作。

完整代码：

#include <stdio.h>

#define MAX_HEAP_SIZE 100

// 定义最小堆结构
struct MinHeap {
    int arr[MAX_HEAP_SIZE];
    int size;
};

// 函数声明
void initHeap(struct MinHeap* heap);
void insertElement(struct MinHeap* heap, int value);
void deleteMin(struct MinHeap* heap);
void printHeap(struct MinHeap* heap);

int main() {
    struct MinHeap heap;
    initHeap(&heap);

    // 添加元素
    insertElement(&heap, 5);
    insertElement(&heap, 3);
    insertElement(&heap, 8);
    insertElement(&heap, 1);

    // 打印堆
    printf("堆的元素：");
    printHeap(&heap);

    // 删除最小元素
    deleteMin(&heap);

    // 打印堆
    printf("删除最小元素后的堆：");
    printHeap(&heap);

    return 0;
}

// 初始化堆
void initHeap(struct MinHeap* heap) {
    heap->size = 0;
}

// 向堆中插入元素
void insertElement(struct MinHeap* heap, int value) {
    if (heap->size == MAX_HEAP_SIZE) {
        printf("堆已满\n");
        return;
    }

    // 将新元素添加到末尾
    heap->arr[heap->size] = value;
    heap->size++;

    // 上移操作，维护堆的性质
    int currentIndex = heap->size - 1;
    while (currentIndex > 0) {
        int parentIndex = (currentIndex - 1) / 2;
        if (heap->arr[currentIndex] < heap->arr[parentIndex]) {
            // 交换元素，保持堆的性质
            int temp = heap->arr[currentIndex];
            heap->arr[currentIndex] = heap->arr[parentIndex];
            heap->arr[parentIndex] = temp;
        } else {
            break; // 堆的性质已满足
        }
        currentIndex = parentIndex;
    }
}

// 删除堆中的最小元素
void deleteMin(struct MinHeap* heap) {
    if (heap->size == 0) {
        printf("堆为空\n");
        return;
    }

    // 将最后一个元素替换到根节点
    heap->size--;
    heap->arr[0] = heap->arr[heap->size];

    // 下移操作，维护堆的性质
    int currentIndex = 0;
    while (1) {
        int leftChild = 2 * currentIndex + 1;
        int rightChild = 2 * currentIndex + 2;
        int minIndex = currentIndex;

        if (leftChild < heap->size && heap->arr[leftChild] < heap->arr[minIndex]) {
            minIndex = leftChild;
        }
        if (rightChild < heap->size && heap->arr[rightChild] < heap->arr[minIndex]) {
            minIndex = rightChild;
        }

        if (minIndex != currentIndex) {
            // 交换元素，保持堆的性质
            int temp = heap->arr[currentIndex];
            heap->arr[currentIndex] = heap->arr[minIndex];
            heap->arr[minIndex] = temp;
            currentIndex = minIndex;
        } else {
            break; // 堆的性质已满足
        }
    }
}

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

   这段代码实现了一个最小堆数据结构，并提供了初始化堆、插入元素、删除最小元素和打印堆的功能。下面是对代码的解析：

1. 定义了一个名为MinHeap的结构体，包含一个整型数组arr和一个整型变量size，用于存储堆的元素和当前堆的大小。

2. 函数声明部分包括了四个函数：initHeap、insertElement、deleteMin和printHeap。这些函数分别用于初始化堆、向堆中插入元素、删除最小元素和打印堆的元素。

3. main函数是程序的入口点。首先创建了一个MinHeap类型的变量heap，然后调用initHeap函数进行初始化。

4. 接下来，通过循环调用insertElement函数向堆中插入了四个元素：5、3、8和1。

5. 然后，调用printHeap函数打印堆的元素，输出结果为：5 3 8 1。

6. 接着，调用deleteMin函数删除堆中的最小元素，即删除元素1。

7. 最后，再次调用printHeap函数打印堆的元素，输出结果为：5 3 8。

    总结起来，这段代码实现了一个简单的最小堆数据结构，并演示了如何向堆中插入元素、删除最小元素以及打印堆的元素。