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

2026/9/13 7:33:08 拓冰建站浏览量

上文：Redis的实现五：二叉堆的数据结构和TTL、c，c++的实现-CSDN博客

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

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

结构特点：
- 二叉堆是一颗完全二叉树，这意味着除了最后一层，其他层都是完全填充的，而且最后一层的节点都尽量靠左排列。
- 在最大堆中，每个节点的值都大于或等于其子节点的值；在最小堆中，每个节点的值都小于或等于其子节点的值。
数组表示：
- 二叉堆可以使用数组来表示。对于给定索引 i，其左子节点的索引为 2i+1，右子节点的索引为 2i+2，父节点的索引为 (i-1)/2。
- 这种数组表示使得堆的访问和修改操作更加高效。
堆的操作：
- 插入：将新元素添加到堆的末尾，然后通过一系列交换操作，使得堆的性质得以保持。
- 删除：删除堆顶元素后，将堆的最后一个元素移到堆顶，然后通过一系列交换操作，使得堆的性质得以保持。
- 堆化：通过自上而下的或自下而上的方式，确保堆的性质得以保持。
时间复杂度：
- 插入和删除操作的时间复杂度为O(log n)，其中n是堆中元素的个数。
- 构建堆的时间复杂度为O(n)，其中n是堆中元素的个数。
应用：
- 优先队列：由于能够快速找到最大值或最小值，二叉堆常被用作优先队列的基础数据结构。
- 堆排序：利用最大堆或最小堆实现的堆排序算法是一种高效的排序算法。

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

完整代码：

#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");
}

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

定义了一个名为MinHeap的结构体，包含一个整型数组arr和一个整型变量size，用于存储堆的元素和当前堆的大小。
函数声明部分包括了四个函数：initHeap、insertElement、deleteMin和printHeap。这些函数分别用于初始化堆、向堆中插入元素、删除最小元素和打印堆的元素。
main函数是程序的入口点。首先创建了一个MinHeap类型的变量heap，然后调用initHeap函数进行初始化。
接下来，通过循环调用insertElement函数向堆中插入了四个元素：5、3、8和1。
然后，调用printHeap函数打印堆的元素，输出结果为：5 3 8 1。
接着，调用deleteMin函数删除堆中的最小元素，即删除元素1。
最后，再次调用printHeap函数打印堆的元素，输出结果为：5 3 8。

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

建站实战干货

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