数据结构—小堆的实现

前言：前面我们已经学习了二叉树，今天我们来学习堆，堆也是一个二叉树，堆有大堆有小堆，大堆父节点大于子节点，小堆父节点总小于子节点，我们在学习C语言的时候也有一个堆的概念，那个堆是操作系统中的堆，与我们今天所学的堆全然不同。我们就来实现下小堆。

在这里插入图片描述

堆的实现：

1.堆的创建

typedef int HPDataType;

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

前面我们已经知道了二叉树用数组来储存比较简单，而且便于访问，所以我们用数组来实现。

2.堆的一些接口

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.堆接口的实现

初始化堆：

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;
		}
	}
}

我们在给堆插入数据时，为了保持小堆就要进行向上调整，如果子节点比父节点要小的话就要和父节点互换。

插入数据：

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.测试代码

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

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

	return 0;
}

我们创建一个数组将它放入小堆里存储，然后我们实现给堆里的数据打印出来。
在这里插入图片描述

打印小堆里的前k个数据：

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

	return 0;
}

我们只要循环去访问堆的根节点就可以了。这里是引用

4.代码的完整实现
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);

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;
		}
	}
}

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;
}

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/187397.html

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

相关文章

栈和队列OJ题目——C语言

栈和队列OJ题目——C语言

目录 LeetCode 20、有效的括号 题目描述&#xff1a; 思路解析&#xff1a; 解题代码&#xff1a; 通过代码&#xff1a; LeetCode 225、用队列实现栈 题目描述&#xff1a; 思路解析&#xff1a; 解题代码&#xff1a; 通过代码&#xff1a; LeetCode 232、用栈…
阅读更多...
C/C++ 运用Npcap发送UDP数据包

C/C++ 运用Npcap发送UDP数据包

Npcap 是一个功能强大的开源网络抓包库&#xff0c;它是 WinPcap 的一个分支&#xff0c;并提供了一些增强和改进。特别适用于在 Windows 环境下进行网络流量捕获和分析。除了支持通常的网络抓包功能外&#xff0c;Npcap 还提供了对数据包的拼合与构造&#xff0c;使其成为实现…
阅读更多...
HarmonyOS简述及开发环境搭建

HarmonyOS简述及开发环境搭建

一、HarmonyOS简介 1、介绍 HarmonyOS是一款面向万物互联时代的、全新的分布式操作系统。有三大系统特性&#xff0c;分别是&#xff1a;硬件互助&#xff0c;资源共享&#xff1b;一次开发&#xff0c;多端部署&#xff1b;统一OS&#xff0c;弹性部署。 HarmonyOS通过硬件互…
阅读更多...
洛谷P1049装箱问题 ————递归+剪枝+回溯

洛谷P1049装箱问题 ————递归+剪枝+回溯

没没没没没没没没没错&#xff0c;又是一道简单的递归&#xff0c;只不过加了剪枝&#xff0c;我已经不想再多说&#xff0c;这道题写了一开始写了普通深搜&#xff0c;然后tle了一个点&#xff0c;后面改成剪枝&#xff0c;就ac了&#xff0c;虽然数据很水&#xff0c;但是不妨…
阅读更多...
第96步 深度学习图像目标检测：FCOS建模

第96步 深度学习图像目标检测：FCOS建模

基于WIN10的64位系统演示 一、写在前面 本期开始&#xff0c;我们继续学习深度学习图像目标检测系列&#xff0c;FCOS&#xff08;Fully Convolutional One-Stage Object Detection&#xff09;模型。 二、FCOS简介 FCOS&#xff08;Fully Convolutional One-Stage Object D…
阅读更多...
iOS强引用引起的内存泄漏

iOS强引用引起的内存泄漏

项目中遇到一个问题&#xff1a; 1.在A页面的ViewDidLoad 方法里写了一个接收通知的方法&#xff0c;如下图&#xff1a; 然后在B页面发送通知 &#xff08;注&#xff1a;下图的NOTI 是 [NSNotificationCenter defaultCenter] 的宏&#xff0c; 考虑一下可能有小白看这篇文章…
阅读更多...
物联网中基于信任的安全性调查研究：挑战与问题

物联网中基于信任的安全性调查研究：挑战与问题

A survey study on trust-based security in Internet of Things: Challenges and issues 文章目录 a b s t r a c t1. Introduction2. Related work3. IoT security from the one-stop dimension3.1. Output data related security3.1.1. Confidentiality3.1.2. Authenticity …
阅读更多...
【vue_2】创建一个弹出权限不足的提示框

【vue_2】创建一个弹出权限不足的提示框

定义了一个名为 getUserRole 的 JavaScript 函数&#xff0c;该函数接受一个参数 authorityId&#xff0c;根据这个参数的不同值返回相应的用户角色字符串。这段代码的目的是根据传入的 authorityId 值判断用户的角色&#xff0c;然后返回相应的角色名称。 如果 authorityId 的…
阅读更多...
Visual Studio 中文注释乱码解决方案

Visual Studio 中文注释乱码解决方案

在公司多人开发项目中经常遇到拉到最新代码&#xff0c;发现中文注释都是乱码&#xff0c;很是emjoy..... 这是由于编码格式不匹配造成的&#xff0c;如果你的注释是 UTF-8 编码&#xff0c;而文件编码是 GBK 或者其他编码&#xff0c;那么就会出现乱码现象。一般的解决办法是…
阅读更多...
STM32-使用固件库新建工程

STM32-使用固件库新建工程

参考链接: 【入门篇】11-新建工程—固件库版本&#xff08;初学者必须认认真真看&#xff09;_哔哩哔哩_bilibili 使用的MCU是STM32F103ZET6 。 这篇参考的是野火的资料&#xff0c;可以在“野火大学堂”或者它的论坛上下载。&#xff08;我通常是野火和正点原子的资料混着看的…
阅读更多...
【AI认证笔记】NO.2人工智能的发展

【AI认证笔记】NO.2人工智能的发展

目录 一、人工智能的发展里程碑 二、当前人工智能的发展特点 1.人工智能进入高速发展阶段 2.人工智能元年 三、人工智能高速发展的三大引擎 1.算法突破 2.算力飞跃 3.数据井喷 四、AI的机遇 五、AI人才的缺口 六、行业AI 人工智能算法&#xff0c;万物互联&#xff…
阅读更多...
基于mediapipe的人手21点姿态检测模型—CPU上检测速度惊人

基于mediapipe的人手21点姿态检测模型—CPU上检测速度惊人

前期的文章，我们介绍了MediaPipe对象检测与对象分类任务，也分享了MediaPipe的人手手势识别。在进行人手手势识别前，MediaPipe首先需要进行人手的检测与人手坐标点的检测，经过以上的检测后，才能把人手的坐标点与手势结合起来，进行相关的手势识别。 MediaPipe人手坐标点检测…
阅读更多...
案例022:基于微信小程序的行政复议在线预约系统

案例022:基于微信小程序的行政复议在线预约系统

文末获取源码 开发语言&#xff1a;Java 框架&#xff1a;SSM JDK版本&#xff1a;JDK1.8 数据库&#xff1a;mysql 5.7 开发软件&#xff1a;eclipse/myeclipse/idea Maven包&#xff1a;Maven3.5.4 小程序框架&#xff1a;uniapp 小程序开发软件&#xff1a;HBuilder X 小程序…
阅读更多...
将 Hexo 部署到阿里云轻量服务器（保姆级教程）

将 Hexo 部署到阿里云轻量服务器（保姆级教程）

将 Hexo 部署到阿里云轻量服务器（保姆级教程） 顺哥轻创 1 前言 作为有梦想的，有追求的程序员，有一个自己的个人博客简直就是必须品。你可以选择 wordpress 这种平台，直接使用，在任何地方只要有网络就能写博客。还可以选择 hexo 这种静态博客，但是发文章就没有那么随心…
阅读更多...
CentOS7安装Docker运行环境

CentOS7安装Docker运行环境

1 引言 Docker 是一个用于开发&#xff0c;交付和运行应用程序的开放平台。Docker 使您能够将应用程序与基础架构分开&#xff0c;从而可以快速交付软件。借助 Docker&#xff0c;您可以与管理应用程序相同的方式来管理基础架构。通过利用 Docker 的方法来快速交付&#xff0c;…
阅读更多...
爬虫项目实战：利用基于selenium框架的爬虫模板爬取豆瓣电影Top250

爬虫项目实战：利用基于selenium框架的爬虫模板爬取豆瓣电影Top250

&#x1f44b; Hi, I’m 货又星&#x1f440; I’m interested in …&#x1f331; I’m currently learning …&#x1f49e; I’m looking to collaborate on …&#x1f4eb; How to reach me … README 目录&#xff08;持续更新中&#xff09; 各种错误处理、爬虫实战及模…
阅读更多...
VRRP的交换机VRRP主备配置例子

VRRP的交换机VRRP主备配置例子

拓朴如下&#xff1a; 主要配置如下&#xff1a; [S1] vlan batch 10 20 # interface Vlanif10ip address 10.1.1.1 255.255.255.0vrrp vrid 1 virtual-ip 10.1.1.254vrrp vrid 1 priority 200vrrp vrid 1 preempt-mode timer delay 20 # interface Vlanif20ip address 13.1.1…
阅读更多...
死磕Nacos系列：Nacos在我的SpringCloud项目中做了什么？

死磕Nacos系列：Nacos在我的SpringCloud项目中做了什么？

Nacos服务注册 我们一个SpringCloud项目中集成了Nacos&#xff0c;当项目启动成功后&#xff0c;就可以在Nacos管理界面上看到我们项目的注册信息&#xff0c;还可以看到项目的健康状态等等信息&#xff1a; 那Nacos是什么时候进行了哪些操作的呢&#xff1f;今天我们来一探究…
阅读更多...
【从浅识到熟知Linux】基本指定之find、grep、head和tail

【从浅识到熟知Linux】基本指定之find、grep、head和tail

&#x1f388;归属专栏&#xff1a;从浅学到熟知Linux &#x1f697;个人主页&#xff1a;Jammingpro &#x1f41f;每日一句&#xff1a;一篇又一篇&#xff0c;学写越上头。 文章前言&#xff1a;本文介绍find、grep、head和tail指令用法并给出示例和截图。 文章目录 find基本…
阅读更多...
Jquery ajax 进行网络请求，同步阻塞引起的UI线程阻塞 （loading图片不显示 ）

Jquery ajax 进行网络请求，同步阻塞引起的UI线程阻塞 （loading图片不显示 ）

jax重新获取数据刷新页面功能&#xff0c;因为ajax属于耗时操作&#xff0c;想在获取数据且加载页面时显示加载遮罩层&#xff0c;结果发现了ajax的好多坑。 ajax 执行http网络请示时时&#xff0c;让遮罩层显示&#xff0c;ajax加载完毕后遮罩层消失。 因为我想让loadChart()…
阅读更多...
最新文章

Copyright @ 2022~2023