当前位置： 首页 > article >正文

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

article 2025/1/22 5:11:21

一、堆的概念

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.kler.cn/a/513044.html

相关文章：

  • 【Vim Masterclass 笔记25】S10L45：Vim 多窗口的常用操作方法及相关注意事项
  • Ubuntu cuda-cudnn中断安装如何卸载
  • 工业制造离不开的BOM
  • 7. 计算机视觉
  • 微服务与docker
  • Kinova仿生机械臂Gen3搭载BOTA 力矩传感器SeneOne:彰显机器人触觉 AI 与六维力传感的融合力量
  • yolo系列模型为什么坚持使用CNN网络？
  • LeetCode：37. 解数独
  • [Easy] leetcode-500 键盘行
  • Pix2Pix：图像到图像转换的条件生成对抗网络深度解析
  • 实现一个自己的spring-boot-starter，基于SQL生成HTTP接口
  • 分布式系统通信解决方案：Netty 与 Protobuf 高效应用
  • 如何打造高效同城O2O平台？外卖跑腿系统源码选型与开发指南
  • 新能源工厂如何借助防静电手环监控系统保障生产安全
  • 0基础跟德姆（dom）一起学AI 自然语言处理19-输出部分实现
  • .NET Core 中如何构建一个弹性HTTP 请求机制
  • Linux应用编程（五）USB应用开发-libusb库
  • 力扣-数组-350 两个数组的交集Ⅱ
  • 连接池偶现15分钟超时问题
  • 数组-二分查找
  • qt中透明度表示
  • 如何使用 Python 进行文件读写操作？
  • 【Linux】Socket编程-TCP构建自己的C++服务器
  • VUE之Router使用及工作模式
  • Oracle LiveLabs实验：Database 19c - JSON
  • AI Workflow AI Agent：架构、模式与工程建议