堆的实现（C语言详解版）

devtools/2025/1/23 12:42:49/

一、堆的概念

1.概念

堆（Heap）是一种特殊的完全二叉树，它满足父节点的值总是不大于或不小于其子节点的值。这种数据结构常用于实现优先队列，以及在各种排序算法中快速找到最大或最小元素。

堆分为两种类型：最大堆和最小堆。

在最大堆中，父节点的值总是大于或等于子节点的值

而在最小堆中，父节点的值总是小于或等于子节点的值。 

大根堆
大根堆
小根堆
小根堆
 

 

2.重点

  • 堆总是一个完全二叉树

  • 堆的物理逻辑其实就是数组

  • leftchild = parent * 2 + 1

  • rightchild = parent * 2 + 2

  • parent = (child - 1) / 2 

上面标红的三个规律非常重要，在后续的向上调整和向下调整中很有用。

上面的大根堆和小根堆的物理存储逻辑为方便大家理解，下方给大家提供了对应的图片

大根堆存储结构
小根堆存储结构​​

大家可以按照上方的标红的三点来对应一下，是不是对应的关系是一致的。接下来就让我们来实现一下堆吧。

二、堆的实现

2.1.头文件设计

typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;//初始化堆
void HpInit(Heap* php, int capacity);
//销毁堆
void HpDestory(Heap* php);
//入堆
void HpPush(Heap* php, HPDataType x);
//出堆
void HpPop(Heap* php);
//返回堆顶元素
HPDataType HpTop(Heap* php);
//查看堆是否为空
bool HpEmpty(Heap* php);
//向下调整
void HpAgjustDown(Heap* php, int parent);
//向上调整
void HpAgjustUp(Heap* php, int child);

因为堆的存储结构是数组形式，所以我们的结构体设计也按照数组来设计就好。 

2.2.初始化&销毁堆

堆的初始化和销毁很简单，我就不细讲了，直接为大家呈现代码啦！

void HpInit(Heap* php, int capacity)
{php->a = (HPDataType*)malloc(sizeof(HPDataType) * capacity);if (php->a == NULL){return;}php->capacity = capacity;php->size = 0;
}void HpDestory(Heap* php)
{free(php->a);php->a = NULL;php->capacity = 0;php->size = 0;
}

2.3 向上调整（Heapify Up）

在堆数据结构中，我们通常采用数组来存储元素，这样做可以有效地节省空间。然而，当我们向堆中插入新元素时，如果简单地将新元素添加到数组的末尾，可能会破坏堆的结构特性。为了保持大根堆和小根堆的有序性，我们需要执行一个重要的操作：向上调整（Heapify Up）。

2.3.1 为什么需要向上调整？

向上调整是必要的，因为它确保了新插入的元素能够被放置在正确的位置，以维持堆的性质。在大根堆中，每个父节点的值都应大于或等于其子节点的值；在小根堆中，每个父节点的值都应小于或等于其子节点的值。如果不进行向上调整，新插入的元素可能会违反这些规则，导致堆结构的破坏。

2.3.2 如何执行向上调整？

向上调整的过程如下：

  1. 定位新元素：找到新插入元素在数组中的位置。

  2. 比较父节点：将新元素与其父节点进行比较。

  3. 交换元素：如果新元素违反了堆的性质（对于大根堆，新元素大于父节点；对于小根堆，新元素小于父节点），则与父节点交换位置。

  4. 重复过程：继续比较新位置的元素与其新的父节点，重复交换过程，直到新元素满足堆的性质或到达根节点。

2.3.2.1 示例

假设我们有一个大根堆，其数组表示如下：

索引：  1    2    3    4
值：   43   9   36   4

现在，我们向堆中插入一个新元素 10，并将其添加到数组的末尾：

索引：  1    2    3    4    5
值：   43   9   36   4    10

为了保持大根堆的性质，我们需要对新元素 10 进行向上调整：

索引：  1    2    3    4    5
值：   43  10   36   4    9

最终，堆的结构得以保持：

索引：  1    2    3    4    5
值：   43  10   36   4    9

通过向上调整，我们确保了堆的有序性，这对于堆排序和其他基于堆的算法至关重要。

2.3.3 代码实现

void Swap(HPDataType* a, HPDataType* b) {HPDataType tmp = *a;*a = *b;*b = tmp;
}void HpAgjustUp(Heap* php, int child) {while (child > 0) {int parent = (child - 1) / 2; // 计算父节点索引if (php->a[child] > php->a[parent]) { // 对于大根堆，比较子节点和父节点Swap(&php->a[child], &php->a[parent]); // 交换位置child = parent; // 更新子节点索引为父节点索引，继续向上调整} else {break; // 如果子节点不大于父节点，调整结束}}
}

2.4 向下调整（Heapify Down）

向下调整（Heapify Down）是堆操作中的另一个核心步骤，它主要用于在删除堆顶元素或重新组织堆时维护堆的结构。与向上调整类似，向下调整确保了堆的有序性，但方向相反，是从上到下进行调整。

2.4.1 为什么需要向下调整？

向下调整是必要的，因为它确保了在删除或替换根节点后，堆的结构能够被正确地维护。在大根堆中，每个父节点的值都应大于或等于其子节点的值；在小根堆中，每个父节点的值都应小于或等于其子节点的值。如果不进行向下调整，新根节点可能会违反这些规则，导致堆结构的破坏。

2.4.2 如何执行向下调整？

向下调整的过程如下：

  1. 定位新根节点：找到需要向下调整的元素在数组中的位置，这通常是新根节点。

  2. 比较子节点：将新根节点与其子节点进行比较。

  3. 交换元素：如果新根节点违反了堆的性质（对于大根堆，新根节点小于子节点中的最大值；对于小根堆，新根节点大于子节点中的最小值），则与子节点中满足条件的元素交换位置。

  4. 重复过程：继续比较新位置的元素与其子节点，重复交换过程，直到新元素满足堆的性质或到达叶子节点。

2.4.2.1 示例

假设我们有一个大根堆，其数组表示如下：

索引：  1    2    3    4    5
值：   43  10   36   4    9

现在，我们从堆中删除根节点 43，并用数组的最后一个元素 9 替换它：

索引：  1    2    3    4    5
值：    9  10   36   4    ?

为了保持大根堆的性质，我们需要对新根节点 9 进行向下调整：

索引：  1    2    3    4    5
值：   36  10   9    4    ?

最终，堆的结构得以保持：

索引：  1    2    3    4    5
值：   36  10   9    4    ?

通过向下调整，我们确保了即使在删除元素后，堆仍然保持其有序性，这对于堆排序和其他基于堆的算法至关重要。

2.4.3 代码实现

void HpAgjustDown(Heap* php, int parent) {int child = parent * 2 + 1; // 计算左子节点索引while (child < php->size) {if (child + 1 < php->size && php->a[child + 1] > php->a[child]) {child++; // 如果右子节点存在且大于左子节点，选择右子节点}if (php->a[child] > php->a[parent]) { // 对于大根堆，比较子节点和父节点Swap(&php->a[child], &php->a[parent]); // 交换位置parent = child; // 更新父节点索引为子节点索引，继续向下调整child = parent * 2 + 1; // 重新计算子节点索引} else {break; // 如果子节点不大于父节点，调整结束}}
}

现在我们已经了解了关于堆的关键，向上调整和向下调整接下来让我实现堆的其他功能吧

2.5 删除堆顶元素

删除堆顶元素是堆操作中的一个重要功能，通常用于优先队列中移除当前最优先的元素。在最大堆中，堆顶是最大元素；在最小堆中，堆顶是最小元素。

2.5.1实现方法

删除堆顶元素通常涉及以下步骤：

  1. 将堆顶元素与堆的最后一个元素交换。

  2. 减小堆的大小，实质上是移除最后一个元素（原堆顶元素）。

  3. 对新的堆顶元素进行向下调整，以恢复堆的性质。

2.5.2代码实现

void HpPop(Heap* php) {if (HpEmpty(php)) {fprintf(stderr, "堆为空，无法删除堆顶元素。\n");return;}// 将堆顶元素与最后一个元素交换php->a[0] = php->a[--php->size];// 对新的堆顶元素进行向下调整HpAgjustDown(php, 0);
}

2.6 插入元素

插入元素是向堆中添加新元素的操作，这在优先队列中非常常见，用于增加新的优先级元素。

2.6.1实现方法

插入元素通常涉及以下步骤：

  1. 增加堆的大小，并把新元素放在堆的末尾。

  2. 对新元素进行向上调整，以恢复堆的性质。

2.6.2代码实现

void HpPush(Heap* php, HPDataType x) {if (php->size == php->capacity) {// 如果堆已满，需要扩容int newCapacity = php->capacity == 0 ? 1 : php->capacity * 2;HPDataType* newArray = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newCapacity);if (!newArray) {fprintf(stderr, "内存分配失败。\n");exit(EXIT_FAILURE);}php->a = newArray;php->capacity = newCapacity;}// 将新元素添加到堆的末尾php->a[php->size++] = x;// 对新元素进行向上调整HpAgjustUp(php, php->size - 1);
}

2.7 返回堆顶元素

该操作用于获取堆中最大（在最大堆中）或最小（在最小堆中）的元素，而无需从堆中移除该元素。这在实现优先队列时尤其有用，因为它允许我们查看当前优先级最高的元素。

2.7.1实现方法

由于堆通常用数组实现，且堆顶元素总是位于数组的第一个位置（索引为0），因此实现此操作相对简单。

2.7.2代码实现

HPDataType HpTop(Heap* php) {// 检查堆是否为空if (HpEmpty(php)) {fprintf(stderr, "堆为空，无法获取堆顶元素。\n");return -1;  // 或者可以选择返回一个特殊值，表示堆为空}// 直接返回数组的第一个元素，即堆顶元素return php->a[0];
}

2.8 返回堆的元素数量

此操作返回堆中元素的数量，这有助于我们了解堆的当前大小，对于动态调整堆的大小等场景非常有用。

2.8.1实现方法

由于堆的元素数量由堆结构体中的size字段直接维护，因此返回这个值是一个直接的操作。

2.8.2代码实现

int HeapSize(Heap* php) {// 检查堆指针是否为空if (php == NULL) {fprintf(stderr, "堆指针无效。\n");return -1;  // 或者可以选择返回一个特殊值，表示非法操作}// 返回堆当前的元素数量return php->size;
}

2.9 查看堆是否为空

检查堆是否为空是一个重要的操作，它可以避免我们在空堆上执行非法操作，如删除元素或获取堆顶元素。

2.9.1实现方法

我们可以通过检查堆的size字段是否为0来判断堆是否为空。

2.9.2代码实现

bool HpEmpty(Heap* php) {// 检查堆指针是否为空if (php == NULL) {fprintf(stderr, "堆指针无效。\n");return true;  // 非法指针视为空堆}// 如果size为0，表示堆为空return php->size == 0;
}

三、完整代码

头文件

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>																																																									
typedef int HPDataType;typedef struct Heap
{HPDataType* a;int size;int capacity;
}Heap;
//初始化堆
void HpInit(Heap* php, int capacity);
//销毁堆
void HpDestory(Heap* php);
//入堆
void HpPush(Heap* php, HPDataType x);
//出堆
void HpPop(Heap* php);
//返回堆顶元素
HPDataType HpTop(Heap* php);
//查看堆是否为空
bool HpEmpty(Heap* php);
//向下调整
void HpAgjustDown(Heap* php, int parent);
//向上调整
void HpAgjustUp(Heap* php, int child);
void HeapSort(int* a, int n);

测试文件

#include "Heap.h"void PrintArray(int* a, int n)
{for (int i = 0; i < n; ++i){printf("%d ", a[i]);}printf("\n");
}int main()
{int arr[] = { 3, 1, 6, 5, 2, 4 };int n = sizeof(arr) / sizeof(arr[0]);printf("Before sorting:\n");PrintArray(arr, n);HeapSort(arr, n);printf("After sorting:\n");PrintArray(arr, n);return 0;
}

实现文件

#include"Heap.h"
void HpInit(Heap* php, int capacity)
{php->a = (HPDataType*)malloc(sizeof(HPDataType) * capacity);if (php->a == NULL){return;}php->capacity = capacity;php->size = 0;
}
void HpDestory(Heap* php)
{free(php->a);php->a = NULL;php->capacity = 0;php->size = 0;
}
void Swap(HPDataType* a, HPDataType* b)
{HPDataType tmp = *a;*a = *b;*b = tmp;
}
void HpAgjustUp(Heap* php, int child)
{while (child > 0){	int parent = (child - 1) / 2;if (php->a[child] > php->a[parent]){Swap(&php->a[child], &php->a[parent]);child = parent;}else{break;}}
}
void HpPush(Heap* php, HPDataType x)
{if (php->size == php->capacity){php->capacity == 0 ? 4 : php->capacity * 2;php->a = (HPDataType*)realloc(php->a, sizeof(HPDataType) * php->capacity);}php->a[php->size] = x;php->size++;HpAgjustUp(php, php->size - 1);
}
bool HpEmpty(Heap* php)
{return php->size == 0;
}
void HpAgjustDown(Heap* php, int parent)
{int child = parent * 2 + 1;while (child < php->size){if (child + 1 < php->size && php->a[child + 1] > php->a[child]){child++;}if (php->a[child] > php->a[parent]){Swap(&php->a[child], &php->a[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}
void HpPop(Heap* php)
{if (HpEmpty(php)){return;}Swap(&php->a[0], &php->a[php->size - 1]);php->size--;int parent = 0;HpAgjustDown(php, parent);
}
HPDataType HpTop(Heap* php)
{return php->a[0];
}
void HeapSort(int* a, int n)
{Heap hp;HpInit(&hp, n);for (int i = 0; i < n; ++i){HpPush(&hp, a[i]);}for (int i = n - 1; i >= 0; i--){a[i] = HpTop(&hp);HpPop(&hp);}HpDestory(&hp);
}

有什么问题欢迎留言哟！ 给个小心心吧


http://www.ppmy.cn/devtools/152881.html

相关文章

提升 Go 开发效率的利器：calc_util 工具库

提升 Go 开发效率的利器：calc_util 工具库

提升 Go 开发效率的利器&#xff1a;calc_util 工具库 在日常开发中&#xff0c;我们常常需要处理数组&#xff08;切片&#xff09;的交集、差集、并集操作&#xff0c;或者更新和过滤数据。尽管这些功能可以手动实现&#xff0c;但重复的逻辑代码不仅影响效率&#xff0c;也…
阅读更多...
卸载和安装Git小乌龟、git基本命令

卸载和安装Git小乌龟、git基本命令

卸载 Git 打开控制面板&#xff1a; 按 Win R 打开运行对话框&#xff0c;输入 control 并按回车键。或直接在功能搜索里搜索“控制面板”。在控制面板中&#xff0c;选择“程序”或“程序和功能”。 查找并卸载 Git&#xff1a; 在程序列表中找到“Git”或“Git for Windows…
阅读更多...
Python网络自动化运维---SSH模块

Python网络自动化运维---SSH模块

目录 SSH建立过程 实验环境准备 一.SSH模块 1.1.Paramiko模块 1.1.1实验代码 1.1.2代码分段讲解 1.1.3代码运行过程 1.2Netmiko模块 Netmiko模块对比paramiko模块的改进&#xff1a; 1.2.1实验代码 1.2.2代码分段讲解 1.2.3代码运行过程 二.Paramiko模块和Ne…
阅读更多...
STL--list（双向链表）

STL--list（双向链表）

目录 一、list 对象创建 1、默认构造函数 2、初始化列表 3、迭代器 4、全0初始化 5、全值初始化 6、拷贝构造函数 二、list 赋值操作 1、赋值 2、assign&#xff08;迭代器1&#xff0c;迭代器2&#xff09; 3、assign&#xff08;初始化列表&#xff09; 4、assig…
阅读更多...
浅谈单例模式

浅谈单例模式

前言 什么是单例模式&#xff1f; 单例模式&#xff0c;属于创建类型的一种常用的软件设计模式。通过单例模式的方法创建的类在当前进程中只有一个实例&#xff08;根据需要&#xff0c;也有可能一个线程中属于单例&#xff0c;如&#xff1a;仅线程上下文内使用同一个实例&am…
阅读更多...
SpringBoot实现定时任务，使用自带的定时任务以及调度框架quartz的配置使用

SpringBoot实现定时任务，使用自带的定时任务以及调度框架quartz的配置使用

SpringBoot实现定时任务&#xff0c;使用自带的定时任务以及调度框架quartz的配置使用 文章目录 SpringBoot实现定时任务&#xff0c;使用自带的定时任务以及调度框架quartz的配置使用一. 使用SpringBoot自带的定时任务&#xff08;适用于小型应用&#xff09;二. 使用调度框架…
阅读更多...
linux系统安装vmware workstation

linux系统安装vmware workstation

linux系统安装vmware workstation 1.下载vmware workstation2.安装vmware workstation&#xff08;使用root用户&#xff09;1.解压2.安装 3.启动vmware workstation 1.下载vmware workstation 访问 https://softwareupdate.vmware.com/cds/vmw-desktop/ws/17.6.2/24409262/li…
阅读更多...
精通Python (13)

精通Python (13)

一&#xff0c;进程和线程 今天我们使用的计算机早已进入多CPU或多核时代&#xff0c;而我们使用的操作系统都是支持“多任务”的操作系统&#xff0c;这使得我们可以同时运行多个程序&#xff0c;也可以将一个程序分解为若干个相对独立的子任务&#xff0c;让多个子任务并发的…
阅读更多...
最新文章

Copyright @ 2022~2023