【数据结构】堆的实现

目录

  • 1. 前言
  • 2. 堆的实现
    • 2.1 初始化
    • 2.2 插入
      • 2.2.1 分析
        • 2.2.1.1 情况一
        • 2.2.1.2 情况二
        • 2.2.1.3 情况三
      • 2.2.2 插入代码实现
        • 2.2.2.1 向上调整代码
    • 2.3 删除
      • 2.3.1 分析
      • 2.3.2 删除代码实现
        • 2.3.2.1 向下调整代码
    • 2.4 找根节点数据
    • 2.5 元素个数
    • 2.6 判空
    • 2.7 销毁
  • 3. 源代码
    • 3.1 Heap.h
    • 3.2 Heap.c
    • 3.3 test.c

1. 前言

在上一篇关于树和二叉树的博客中，最后提到了堆。有小根堆和大根堆。
在这里插入图片描述
左边的结构是我们想象出来的，右边才是实际存储的结构。
这次来实现堆。

2. 堆的实现

用数组来实现，这里以实现小堆为例子，它的特点是父节点小于子节点。
先定义一个堆的结构体：为了方便扩容，加了size。

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

2.1 初始化

刚开始数组中没有数据，置为NILL,此时的size和capacity都为0。
代码实现：

void HeapInit(HP* php)
{
	assert(php);

	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

2.2 插入

2.2.1 分析

2.2.1.1 情况一

在这里插入图片描述
假设插入的数据为30。
那么堆需要处理吗？
在小堆中父亲节点小于子节点。
通过当前位置，计算父节点的下标来判断一下，是否需要调整，显然28是小于30的这里就不需要调整了。

2.2.1.2 情况二

来看看其它情况：
在这里插入图片描述
这里的子节点就小于父节点，这里就要将父节点和子节点交换一下，然后再判断。
在这里插入图片描述
通过下标将两个位置的值交换之后，分析已经是小根堆了，就不继续往前走了。

2.2.1.3 情况三

在这里插入图片描述
这里先将10与它的父节点28比较，发现10比较小，此时就交换它们两个；再往上看，发现18比10小，又交换；再往上，发现15也比10小，此时又交换。
此时就是这样：
在这里插入图片描述
这个过程叫做向上调整。
只要发现父节点小于子节点时就停止向上调整。

2.2.2 插入代码实现

先判断空间是否足够，不够就扩容，够就直接插入x，再将php->size++。

void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		php->a = tmp;
		php->capacity = newCapacity;
	}

	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);
}
2.2.2.1 向上调整代码

从child的位置开始调整，就是刚插入的值，也就是size-1。
先和它的父节点比较，如果小于父节点就交换。这里直接写成while循环，交换之后向上走，将child 的位置给parent，然后parent = (child - 1) / 2，一直向上走，当child=0时结束或者parent >= 0时结束。

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}


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

在这里插入图片描述

2.3 删除

规定删除堆顶数据。

2.3.1 分析

在这里插入图片描述
这时删除堆顶的数据，那么堆顶就是次小的值。
这里要保持删除之后还是小堆。

如果使用挪动数据覆盖，删除根，此时整棵树的父子关系全乱了，大小关系也乱了，这样是不可行的。

使用首尾交换，然后尾删。
在这里插入图片描述
尾删之后，左右子树依旧是小堆。
在这里插入图片描述
把30换上去就结束了吗？
当然不是，使用向下调整算法。
此时不是小堆，就要调整。
与30子节点18比较，18小，它们两个就交换。再向下，25比18小，又交换一次，再向下，27小于30，又交换。最后到叶子节点就结束。
在这里插入图片描述

2.3.2 删除代码实现

首尾交换删除，然后将php->size--，最后向下调整。

void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

	AdjustDown(php->a, php->size, 0);
}

删三次
在这里插入图片描述

2.3.2.1 向下调整代码

当父节点大于子节点时就交换一下，然后继续向下判断大小关系。
这里如果定义左右孩子，左孩子小是一种逻辑，右孩子小也是一种逻辑，就很麻烦。
这里使用一个假设法，就直接定义一个孩子。
假设左孩子小，如果解设错了，更新一下，换到右孩子。
如果孩子小于父亲就交换，然后向下走让parent = child，child = parent * 2 + 1。

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

	while (child < size)
	{
		// 假设左孩子小，如果解设错了，更新一下

		if (child + 1 < size && a[child + 1] < a[child])
		{
			++child;
		}

		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

2.4 找根节点数据

堆顶数据在数组中的位置就是php->a[0]。

HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	return php->a[0];
}

2.5 元素个数

元素的个数就是这个数组的长度，直接返回php->size。

size_t HeapSize(HP* php)
{
	assert(php);

	return php->size;
}

2.6 判空

直接判断一下数组中是否有数据就行，如果php->size == 0为真就是空，为假就不是。

bool HeapEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

2.7 销毁

先断言一下，然后将数组free，再将php->a 置为NULL，最后将php->size 和 php->capacity 置为0。

void HeapDestroy(HP* php)
{
	assert(php);

	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

3. 源代码

3.1 Heap.h

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

typedef int HPDataType;

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

void HeapInit(HP* php);
void HeapDestroy(HP* php);
void HeapPush(HP* php, HPDataType x);
// 规定删除堆顶（根节点）
void HeapPop(HP* php);
HPDataType HeapTop(HP* php);
size_t HeapSize(HP* php);
bool HeapEmpty(HP* php);

3.2 Heap.c

#include"Heap.h"

// 小堆
void HeapInit(HP* php)
{
	assert(php);

	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

void HeapDestroy(HP* php)
{
	assert(php);

	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}


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

// O(logN)
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}

		php->a = tmp;
		php->capacity = newCapacity;
	}

	php->a[php->size] = x;
	php->size++;

	AdjustUp(php->a, php->size - 1);
}



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

	while (child < size)
	{
		// 假设左孩子小，如果解设错了，更新一下

		if (child + 1 < size && a[child + 1] < a[child])
		{
			++child;
		}

		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	Swap(&php->a[0], &php->a[php->size - 1]);
	php->size--;

	AdjustDown(php->a, php->size, 0);
}

HPDataType HeapTop(HP* php)
{
	assert(php);
	assert(php->size > 0);

	return php->a[0];
}

size_t HeapSize(HP* php)
{
	assert(php);

	return php->size;
}

bool HeapEmpty(HP* php)
{
	assert(php);

	return php->size == 0;
}

3.3 test.c

#include"Heap.h"

int main()
{
	int a[] = { 4,6,2,1,5,8,2,9};
	HP hp;
	HeapInit(&hp);
	for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
	{
		HeapPush(&hp, a[i]);
	}

	/*int k = 3;
	while (k--)
	{
		printf("%d\n", HeapTop(&hp));
		HeapPop(&hp);
	}*/

	while (!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
	printf("\n");

	return 0;
}

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

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

相关文章

Walrus 0.4发布：单一配置、多态运行，体验下一代应用交付模型

Walrus 0.4发布：单一配置、多态运行，体验下一代应用交付模型

今天&#xff0c;我们高兴地宣布云原生统一应用平台 Walrus 0.4 正式发布&#xff0c;这是一个里程碑式的版本更新。新版本采用了全新的应用模型——仅需进行单一配置&#xff0c;即可在多种模态的基础设施及环境中运行包括应用服务及周边依赖资源在内的完整应用系统。“You bu…
阅读更多...
构建SQL Server链接服务器：实现跨服务器数据访问及整合

构建SQL Server链接服务器：实现跨服务器数据访问及整合

点击上方蓝字关注我 在SQL Server数据库管理中&#xff0c;链接服务器是一项强大的功能&#xff0c;允许在一个SQL Server实例中访问另一个SQL Server实例的数据。这种功能为数据库管理员提供了灵活性&#xff0c;使其能够跨不同服务器进行数据交互&#xff0c;开辟了更多的应用…
阅读更多...
中科亿海微除法器（DIVIDE）

中科亿海微除法器（DIVIDE）

技术背景 技术概述 FPGA实现除法运算是一个比较复杂的过程&#xff0c;因为硬件逻辑与软件程序的区别。如果其中一个操作数为常数&#xff0c;可以通过简单的移位与求和操作代替&#xff0c;但用硬件逻辑完成两变量间除法运算会占用较多的资源&#xff0c;电路结构复杂&#xf…
阅读更多...
vue.js如何根据后台返回来的图片url进行图片下载

vue.js如何根据后台返回来的图片url进行图片下载

原创/朱季谦 最近在做一个前端vue.js对接的功能模块时&#xff0c;需要实现一个下载图片的功能&#xff0c;后台返回来的是一串图片url&#xff0c;试了很多种方法&#xff0c;发现点击下载时出来的效果&#xff0c;都是跳到一个新的图片网页&#xff0c;后来经过一番琢磨&…
阅读更多...
网络渗透测试（认识）

网络渗透测试（认识）

ARP协议 逻辑地址变成物理地址 32bit的IP地址变换成48bit的mac地址 ARP两个字节&#xff08;0x0806&#xff09; ARP解析协议 每一个主机都有ARP高速缓存&#xff0c;此缓存中记录了最近一段时间的内其他IP地址与其MAC地址的对应关系 如果本机想与某台主机通信&#xff0c;首先…
阅读更多...
关于js的find的基本用法

关于js的find的基本用法

Array.prototype.find() 是 JavaScript 的一个数组方法&#xff0c;它被用来在数组中查找一个符合条件的元素。一旦找到第一个符合条件的元素, find() 会立即返回这个元素的值&#xff0c;否则返回 undefined。 以下是 find() 方法的基本语法&#xff1a; arr.find(callback(el…
阅读更多...
有趣！谷歌AI认定阿波罗登月“造假“

有趣！谷歌AI认定阿波罗登月“造假“

大家好&#xff0c;我是极智视界&#xff0c;欢迎关注我的公众号&#xff0c;获取我的更多前沿科技分享 邀您加入我的知识星球「极智视界」&#xff0c;星球内有超多好玩的项目实战源码和资源下载&#xff0c;链接&#xff1a;https://t.zsxq.com/0aiNxERDq 事情是这样的&#…
阅读更多...
Leetcode—739.每日温度【中等】

Leetcode—739.每日温度【中等】

2023每日刷题&#xff08;四十二&#xff09; Leetcode—739.每日温度 单调栈实现思想 从右到左实现代码 class Solution { public:vector<int> dailyTemperatures(vector<int>& temperatures) {int n temperatures.size();stack<int> st;vector<i…
阅读更多...
win10屏幕录制神器，让你轻松上手！

win10屏幕录制神器，让你轻松上手！

屏幕录制成为了人们日常生活中越来越重要的一部分&#xff0c;无论是游戏录制、在线会议记录&#xff0c;还是教程演示&#xff0c;屏幕录制都能够有效地帮助人们捕捉并分享关键信息。随着windows 10系统的普及&#xff0c;许多用户已经开始探索这个系统中的屏幕录制功能。接下…
阅读更多...
百度手机浏览器关键词排名优化——提升关键词排名 开源百度小程序源码系统 附带完整的搭建教程

百度手机浏览器关键词排名优化——提升关键词排名 开源百度小程序源码系统 附带完整的搭建教程

百度作为国内领先的搜索引擎&#xff0c;一直致力于为用户提供最优质的信息服务。在移动互联网时代&#xff0c;手机浏览器成为了用户获取信息的主要渠道。而小程序作为轻量级的应用程序&#xff0c;具有即用即走、无需下载等优势&#xff0c;越来越受到用户的青睐。然而&#…
阅读更多...
2023年亚太杯APMCM数学建模大赛B题玻璃温室小气候调控

2023年亚太杯APMCM数学建模大赛B题玻璃温室小气候调控

2023年亚太杯APMCM数学建模大赛 B题 玻璃温室小气候调控 原题再现 温室作物的产量受各种气候因素的影响&#xff0c;包括温度、湿度和风速[1]。其中&#xff0c;适宜的温度和风速对植物生长至关重要[2]。为了调节玻璃温室内的温度、风速等气候因素&#xff0c;在温室设计中常…
阅读更多...
深入理解 Docker 核心原理：Namespace、Cgroups 和 Rootfs

深入理解 Docker 核心原理：Namespace、Cgroups 和 Rootfs

来自&#xff1a;探索云原生 https://www.lixueduan.com 原文&#xff1a;https://www.lixueduan.com/posts/docker/03-container-core/ 通过这篇文章你可以了解到 Docker 容器的核心实现原理&#xff0c;包括 Namespace、Cgroups、Rootfs 等三个核心功能。 后续文章会演示如…
阅读更多...
python subprocess

python subprocess

查看python官方文档&#xff1a;最全 p subprocess.Popen([rpng2bdf.exe,[r-o .\tst\myfont.bdf -f myfont -e 65 tst\*.png]],stdoutsubprocess.PIPE,stderr subprocess.PIPE) out,err p.communicate() print(out) 注意&#xff0c;如何将shell命令分解为参数序列可能并…
阅读更多...
01-AI大模型智能客服 V0.1「上」

01-AI大模型智能客服 V0.1「上」

你好&#xff0c;我是悦创。 首发&#xff1a;https://mp.weixin.qq.com/s/6MTkpWZCEbFWOcUn0Vexvw V0.1 版本我将分为上中下三篇进行书写和发布&#xff0c;欢迎分享和我微信进讨论群&#xff1a;Jiabcdefh。 计划&#xff1a; 会迭代好几个版本&#xff0c;看阅读量和点赞…
阅读更多...
工作流能实现自动化吗？应该用什么工具？

工作流能实现自动化吗？应该用什么工具？

研究显示&#xff0c;CRM系统工作流自动化软件不仅能简化冗余的工作且不需要监控和指导就能提高员工的工作效率。企业需要工作流自动化软件吗&#xff1f;答案是肯定的&#xff0c;工作流自动化的好处有哪些&#xff1f; 为什么企业需要工作流自动化软件 每家企业都希望降本增…
阅读更多...
百面深度学习-自然语言处理

百面深度学习-自然语言处理

自然语言处理 神经机器翻译模型经历了哪些主要的结构变化&#xff1f;分别解决了哪些问题&#xff1f; 神经机器翻译&#xff08;Neural Machine Translation, NMT&#xff09;是一种使用深度学习技术来实现自动翻译的方法。自从提出以来&#xff0c;NMT模型经历了几个重要的…
阅读更多...
新品发布 | 聚铭睿合管控巡航平台是什么来头？

新品发布 | 聚铭睿合管控巡航平台是什么来头？

阅读更多...
【刷题笔记】数组-双指针||覆盖||重复元素

【刷题笔记】数组-双指针||覆盖||重复元素

【刷题笔记】数组-双指针||覆盖||重复元素 目录 移除元素删除有序数组中的重复项删除有序数组中的重复项 II分析 移除元素 https://leetcode.cn/problems/remove-element/ 给你一个数组 nums 和一个值 val&#xff0c;你需要 原地 移除所有数值等于 val 的元素&#xff0c;并…
阅读更多...
电商数据采集及数据监测的关注重点

电商数据采集及数据监测的关注重点

当品牌需要做分析报告时&#xff0c;需要用到电商数据&#xff0c;所以分析的前提是数据采集&#xff0c;只有采集的数据越准确&#xff0c;分析的报告才有价值&#xff0c;同样&#xff0c;品牌在做数据监测的基础也是采集&#xff0c;如电商价格监测&#xff0c;需要采集到准…
阅读更多...
Linux多线程基本概念

Linux多线程基本概念

目录 ​编辑 1.什么是进程&#xff0c;线程&#xff0c;并发&#xff0c;并行 优点 缺点 什么资源是线程应该私有的呢 为什么线程切换成本更低呢 3.线程控制 pthread_create lpthread选项 makefile 代码实现 ps -aL 什么是LWP 轻量级进程ID与进程ID之间的区别 LWP与pthr…
阅读更多...
最新文章

Copyright @ 2022~2023