数据结构：堆的三部曲 （一）堆的实现

堆的实现

  • 1.堆的结构
    • 1.1堆的定义理解
  • 2.堆的实现（以小根堆为例）
    • 2.1 堆结构体的定义
    • 2.2 堆的插入
      • 交换函数
      • 向上调整算法
      • 插入函数的代码
    • 2.3 堆的删除
      • 向下调整算法：
      • 删除函数的代码：
    • 2.4其他操作
  • 3.测试以及完整源代码实现
    • 3.1测试代码
  • 3.2完整代码实现
    • heap.c
    • heap.c
    • main.c

1.堆的结构

1.1堆的定义理解

堆的逻辑结构为一颗完全二叉树，堆对于数据存储有一定的要求：这这棵树的任意一颗子树的根节点的值小于等于（或大于等于）其孩子节点的值。我们将根节点最大的堆叫做小堆，把根节点最大的堆叫做大堆。
堆的存储结构结构为数组，我们将堆的元素存储在一个数组之中。由于堆是完全二叉树，所以其节点下标之间满足以下关系：
parent = (child-1) / 2
leftChild = parent2 + 1
rightChild = parent2 + 2 = leftChild + 1

堆的结构如图：
在这里插入图片描述

注意：堆规定的是父亲和孩子之间值的关系，并没有规定左右孩子值之间的关系。比如下图，我们对于15这个父节点的左右孩子大小没有要求，两种情况都可以，因此我们只需要维护父亲和孩子的关系即可。
在这里插入图片描述

2.堆的实现（以小根堆为例）

2.1 堆结构体的定义

由于堆是使用数组来存储的，因此堆的结构定义和顺序表相同，首先需要定义一个数据类型的指针，然后还需要定义int类型的size和capacity，用来记录当前有多少个节点以及当前最多能存储多少节点，当空间不足时我们就可以扩容操作。

typedef int HpDataType;
typedef struct Heap
{
	HpDataType* a;
	int size;
	int capacity;
}HP;

2.2 堆的插入

堆的插入的前提是插入前的二叉树是堆，因此插入数据后只需要保持其父亲节点和孩子节点的关系。由于使用数组存储，因此在size位置插入后，就需要开始调整使插入后仍为堆。

交换函数

void Swap(HpDataType* x, HpDataType* y)
{
	HpDataType tmp = *x;
	*x = *y;
	*y = tmp;
}

向上调整算法

由于是从插入的那个孩子处开始调整，所以需要传入当时的下标。
child即为最后一个节点的下标。由于需要维护每一个父亲和孩子的关系，因此需要用到循环。如果新插入的节点的值比父节点的值小，那么交换它们的值，如果比其的父节点的值大，那么插入节点后的堆仍为小堆，不需要调整，退出循环。考虑最坏情况，如果插入的节点比第一个节点的值都小，那么就需要一直交换，当最后一个节点也调整后，不满足条件从而退出循环，那么这个最坏的结果结束后的child即为最终的循环结束条件，此时child为0，因此循环进行条件为child>0，结束条件为child<=0。

void AdjustUp(HpDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

插入函数的代码

void HPPush(HP* hp, HpDataType x)
{
	assert(hp);
	int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
	//空间如果不足则扩容
	if (hp->capacity == hp->size)
	{
		HpDataType* tmp = (HpDataType*)realloc(hp->a, newcapacity*sizeof(HpDataType));
		if (tmp == NULL)
		{
			perror("realloc failed");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;
	AdjustUp(hp->a, hp->size - 1);
}

2.3 堆的删除

堆的删除为删除堆顶元素。
如果我们直接使用数据移动覆盖的删除方法，那么基本所有的父子关系将会被打乱，这样堆就会被完全破坏，而顺序表删除最后一个元素很容易，因此我们可以将第一个节点和最后一个节点交换，再删除最后一个节点，这样不仅更加简便，而且根节点的左右子树仍为堆，我们只需要将根节点向下调整即可调整为堆。

向下调整算法：

那么如何实现向下调整算法呢？
我们需要让每一颗子树的根节点都为该树的最小值，由于堆没有规定左右孩子之间的关系，因此如果需要向下调整交换时，需要判断该节点的左右孩子的最小值。如果不需要交换，即该节点比孩子节点小，那么就证明此时为堆，结束循环。考虑最坏情况，直到交换到叶子节点才能结束，那么如何判断叶子节点呢？叶子节点是没有孩子的节点，也就是其孩子的下标超出了size的大小，因此通过child和size的大小可以判断是否为叶子节点。

void AdjustDown(HpDataType* a, int size, int parent)
{
	int child = parent * 2 + 1;

	while (child < size)
	{
		//假设左孩子小，如果假设错误则交换
		if (child + 1 < size && a[child] > a[child + 1])
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

删除函数的代码：

void HPPop(HP* hp)
{
	assert(hp);
	assert(hp->size > 0);

	Swap(&hp->a[0], hp->a[hp->size - 1]);
	hp->size--;
	AdjustDown(hp->a, hp->size, 0);
}

2.4其他操作

2.4.1取堆顶元素

int HPTop(HP* hp)
{
	assert(hp);

	return hp->a[0];
}

2.4.2堆的节点个数

int HPSize(HP* hp)
{
	assert(hp);

	return hp->size;
}

2.4.3堆是否为空判断

bool IsEmpty(HP* hp)
{
	assert(hp);

	return hp->size == 0;
}

3.测试以及完整源代码实现

3.1测试代码

int main()
{
	int a[] = { 3,5,2,7,9,4,1 };
	HP hp;
	HPinit(&hp);
	//建堆
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HPPush(&hp, a[i]);
	}
	//打印堆
	for (int i = 0; i < hp.size; i++)
	{
		printf("%d ", hp.a[i]);
	}
	printf("\n");
	//类似堆排序
	while (!IsEmpty(&hp))
	{
		printf("%d ", HPTop(&hp));
		HPPop(&hp);
	}
	printf("\n");
	//类似top  k
	//int k = 3;
	//while (k--)
	//{
	//	printf("%d ", HPTop(&hp));
	//	HPPop(&hp);
	//}

	HPDestroy(&hp);
	return 0;
}

运行结果如下：
在这里插入图片描述

3.2完整代码实现

heap.c

#pragma once

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

typedef int HpDataType;
typedef struct Heap
{
	HpDataType* a;
	int size;
	int capacity;
}HP;

void HPinit(HP* hp);
void HPDestroy(HP* hp);
void HPPush(HP* hp, HpDataType x);
void HPPop(HP* hp);
int HPTop(HP* hp);
bool IsEmpty(HP* hp);
int HPSize(HP* hp);

heap.c

//小堆的实现
void HPinit(HP* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}

void HPDestroy(HP* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->capacity = hp->size = 0;
}

void Swap(HpDataType* x, HpDataType* y)
{
	HpDataType tmp = *x;
	*x = *y;
	*y = tmp;
}

void AdjustUp(HpDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void HPPush(HP* hp, HpDataType x)
{
	assert(hp);
	if (hp->capacity == hp->size)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HpDataType* tmp = (HpDataType*)realloc(hp->a, newcapacity * sizeof(HpDataType));
		if (tmp == NULL)
		{
			perror("realloc failed");
			exit(-1);
		}
		hp->a = tmp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;
	AdjustUp(hp->a, hp->size - 1);
}

void AdjustDown(HpDataType* a, int size, int parent)
{
	int child = parent * 2 + 1;

	while (child < size)
	{
		//假设左孩子小，如果假设错误则交换
		if (child + 1 < size && a[child] > a[child + 1])
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HPPop(HP* hp)
{
	assert(hp);
	assert(hp->size > 0);

	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
	AdjustDown(hp->a, hp->size, 0);
}

int HPTop(HP* hp)
{
	assert(hp);

	return hp->a[0];
}

bool IsEmpty(HP* hp)
{
	assert(hp);

	return hp->size == 0;
}

int HPSize(HP* hp)
{
	assert(hp);

	return hp->size;
}

main.c

#include "heap.h"

int main()
{
	int a[] = { 3,5,2,7,9,4,1 };
	HP hp;
	HPinit(&hp);
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HPPush(&hp, a[i]);
	}
	printf("建堆如下:");
	for (int i = 0; i < hp.size; i++)
	{
		printf("%d ", hp.a[i]);
	}
	printf("\n");
	printf("依次取堆顶元素:");
	while (!IsEmpty(&hp))
	{
		printf("%d ", HPTop(&hp));
		HPPop(&hp);
	}
	printf("\n");
	//int k = 3;
	//while (k--)
	//{
	//	printf("%d ", HPTop(&hp));
	//	HPPop(&hp);
	//}
	HPDestroy(&hp);
	return 0;
}

以上就是本次说有内容，谢谢观看。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/283558.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

山西电力市场日前价格预测【2024-01-02】

山西电力市场日前价格预测【2024-01-02】

日前价格预测 预测说明&#xff1a; 如上图所示&#xff0c;预测明日&#xff08;2024-01-02&#xff09;山西电力市场全天平均日前电价为92.93元/MWh。其中&#xff0c;最高日前电价为275.90元/MWh&#xff0c;预计出现在18:00。最低日前电价为0.00元/MWh&#xff0c;预计出现…
阅读更多...
【数据结构与算法】第1章绪论（头歌习题）【合集】

【数据结构与算法】第1章绪论（头歌习题）【合集】

文章目录 第1关&#xff1a;求和任务描述编程要求代码 第2关&#xff1a;求倒数和的倒数任务描述编程要求完整代码 第3关&#xff1a;回文数任务描述编程要求完整代码 第4关&#xff1a;求素数个数任务描述编程要求完整代码 第5关&#xff1a;最大因子任务描述编程要求完整代码…
阅读更多...
第6课 用window API捕获麦克风数据并加入队列备用

第6课 用window API捕获麦克风数据并加入队列备用

今天是2024年1月1日&#xff0c;新年的第一缕阳光已经普照大地&#xff0c;祝愿看到这篇文章的所有程序员或程序爱好者都能在新的一年里持之以恒&#xff0c;事业有成。 今天也是我加入CSDN的第4100天&#xff0c;但回过头看一看&#xff0c;这么长的时间也没有在CSDN写下几篇…
阅读更多...
2023-刻苦自励,2024-奋起直追！

2023-刻苦自励,2024-奋起直追！

点击上方“嵌入式应用研究院”&#xff0c;选择“置顶/星标公众号” 干货福利&#xff0c;第一时间送达&#xff01; 来源 | 嵌入式应用研究院 整理&排版 | 嵌入式应用研究院 一、引言 时光如影&#xff0c;岁月如梭。转眼之间&#xff0c;2023年已经过去&#xff0c;在这一…
阅读更多...
拒绝采样（算法）总结

拒绝采样（算法）总结

先说说什么是拒绝采样算法&#xff1a;就类似于数学上的求阴影面积的方法&#xff0c;直接求求不出来&#xff0c;就用大面积 - 小面积 阴影面积的办法。 所谓拒绝 和 采样 &#xff1a;就像是撒豆子计个数&#xff0c;计算概率问题一样&#xff0c;大桶里面套小桶&#xff0c…
阅读更多...
[C#]OpenCvSharp结合yolov8-face实现L2CS-Net眼睛注视方向估计或者人脸朝向估计

[C#]OpenCvSharp结合yolov8-face实现L2CS-Net眼睛注视方向估计或者人脸朝向估计

源码地址&#xff1a; github地址&#xff1a;https://github.com/Ahmednull/L2CS-Net L2CS-Net介绍&#xff1a; 眼睛注视&#xff08;eye gaze&#xff09; 是在各种应用中使用的基本线索之一。 它表示用户在人机交互和开放对话系统中的参与程度。此外&#xff0c;它还被用…
阅读更多...
Docker 从入门到实践：Docker介绍

Docker 从入门到实践：Docker介绍

前言 在当今的软件开发和部署领域&#xff0c;Docker已经成为了一个不可或缺的工具。Docker以其轻量级、可移植性和标准化等特点&#xff0c;使得应用程序的部署和管理变得前所未有的简单。无论您是一名开发者、系统管理员&#xff0c;还是IT架构师&#xff0c;理解并掌握Dock…
阅读更多...
【数据结构】栈和队列（队列的基本操作和基础知识）

【数据结构】栈和队列（队列的基本操作和基础知识）

&#x1f308;个人主页&#xff1a;秦jh__https://blog.csdn.net/qinjh_?spm1010.2135.3001.5343&#x1f525; 系列专栏&#xff1a;《数据结构》https://blog.csdn.net/qinjh_/category_12536791.html?spm1001.2014.3001.5482 ​ 目录 前言 队列 队列的概念和结构 队列的…
阅读更多...
域名转移：将腾讯云转移至阿里云

域名转移：将腾讯云转移至阿里云

当时注册域名时&#xff0c;腾讯域云相对便宜&#xff0c;但目前阿里云在业界更加成熟&#xff0c;因此将自己申请的域名由阿里云转移至阿里云&#xff0c;并记录转移过程。 一、域名转出 进入腾讯云&#xff0c;登陆后选择控制台&#xff0c;选择我的资源–域名注册–全部域名…
阅读更多...
【华为机试】2023年真题B卷（python）-滑动窗口最大值

【华为机试】2023年真题B卷（python）-滑动窗口最大值

一、题目 题目描述&#xff1a; 有一个N个整数的数组&#xff0c;和一个长度为M的窗口&#xff0c;窗口从数组内的第一个数开始滑动直到窗口不能滑动为止&#xff0c; 每次窗口滑动产生一个窗口和&#xff08;窗口内所有数的和&#xff09;&#xff0c;求窗口滑动产生的所有窗口…
阅读更多...
LTPI协议的理解——1、LTPI协议的定义和结构

LTPI协议的理解——1、LTPI协议的定义和结构

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 LTPI协议的理解——1、LTPI协议的定义和结构 定义DC-SCM 2.0 LTPI 结构GPIO通道I2C/SMBus通道Uart通道OEM通道数据通道 总结 定义 LTPI (LVDS Tunneling Protocol & Int…
阅读更多...
单片机数据发送程序

单片机数据发送程序

#include<reg51.h> //包含单片机寄存器的头文件 /***************************************************** 函数功能&#xff1a;向PC发送一个字节数据 ***************************************************/ void Send(unsigned char dat) { SBUFdat; whil…
阅读更多...
【ESP-NOW with ESP32：从多个开发板接收数据（多对一）】

【ESP-NOW with ESP32：从多个开发板接收数据（多对一）】

【ESP-NOW with ESP32&#xff1a;从多个开发板接收数据&#xff08;多对一&#xff09;】 1. 项目概况2. 先决条件2.1 环境配置2.2 所需零件 3. 获取接收板 MAC 地址4. ESP32 发送码 &#xff08;ESP-NOW&#xff09;4.1 代码的工作原理4.2 setup&#xff08;&#xff09;4.3 …
阅读更多...
异步处理方案

异步处理方案

目录 1.通过promise的链式调用将异步方法变为同步执行 2.使用async及await 3.回调函数方式 4.三种方式对比 5.async及await使用的注意点 1.通过promise的链式调用将异步方法变为同步执行 function get1(){return new Promise((resolve,reject) >{console.log(执行get1接…
阅读更多...
B端产品学习-市场调研与分析

B端产品学习-市场调研与分析

B端产品市场调研与分析 目录&#xff1a; 为什么要做产品调研 B端产品调研对比C端产品调研 B端产品调研要怎么做 为什么要做产品调研 杰克特劳特说过&#xff1a;“成为唯一。如果不能争得第一&#xff0c;那就找到一个能够成为第一的细分&#xff0c;这就是定位的第一法则…
阅读更多...
激发大规模ClickHouse数据加载(3/3)确保加载大规模数据的可靠性

激发大规模ClickHouse数据加载(3/3)确保加载大规模数据的可靠性

本文字数&#xff1a;7016&#xff1b;估计阅读时间&#xff1a;18 分钟 作者&#xff1a;Tom Schreiber 审校&#xff1a;庄晓东&#xff08;魏庄&#xff09; 本文在公众号【ClickHouseInc】首发 本文是“激发大规模ClickHouse数据加载”系列文章的最后一篇&#xff1a; 激发…
阅读更多...
【华为机试】2023年真题B卷（python）-猴子爬山

【华为机试】2023年真题B卷（python）-猴子爬山

一、题目 题目描述&#xff1a; 一天一只顽猴想去从山脚爬到山顶&#xff0c;途中经过一个有个N个台阶的阶梯&#xff0c;但是这猴子有一个习惯&#xff1a; 每一次只能跳1步或跳3步&#xff0c;试问猴子通过这个阶梯有多少种不同的跳跃方式&#xff1f; 二、输入输出 输入描述…
阅读更多...
springboot基于Java的大学生迎新系统

springboot基于Java的大学生迎新系统

springboot基于Java的大学生迎新系统 源码获取&#xff1a; https://docs.qq.com/doc/DUXdsVlhIdVlsemdX
阅读更多...
Windows磁盘空间占用分析工具-WizTree

Windows磁盘空间占用分析工具-WizTree

文章目录 WizTree作用WizTree树状分析图WizTree特点获取网址 WizTree作用 平时我们电脑用久了&#xff0c;产生很多文件&#xff0c;导致盘符空间不足&#xff0c;但是不知道那些文件占用比较多&#xff0c;这就需要磁盘空间分析工具-WizTree来分析文件占用情况 WizTree树状分…
阅读更多...
信息网络协议基础_绪论

信息网络协议基础_绪论

文章目录 交换技术基本概念电路交换电话交换网 分组交换数据报交换虚电路交换 网络体系结构新的网络技术和体系结构Delay/Disruption Tolerant Networking(DTN)如何理解间隙性&#xff1f; Software Define Networking(SDN)Future Internet ArchitectureNDN(Named Data Network…
阅读更多...
最新文章

Copyright @ 2022~2023