【数据结构与算法】之堆及其实现！

目录

1、堆的概念及结构

2、堆的实现 

2.1 堆向下和向上调整算法

2.2 堆的创建

2.3 建堆时间复杂度

2.4 堆的插入

2.5 堆的删除

2.6 完整代码

3、完结散花

                                                                                个人主页：秋风起，再归来~

                                                                                            数据结构与算法                             

                                                                       个人格言：悟已往之不谏，知来者犹可追

                                                                                        克心守己，律己则安！

1、堆的概念及结构

如果有一个关键码的集合K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足： 且 = 且 >= ) i = 0，1， 2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：

堆中某个节点的值总是不大于或不小于其父节点的值；

堆总是一棵完全二叉树。

2、堆的实现 

2.1 堆向下和向上调整算法

现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整 成一个小堆。向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

int array[] = {27,15,19,18,28,34,65,49,25,37};

代码实现：

1、向上调整算法：

//交换
void swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}


//向下调整
void AdjustDown(HPDataType* 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、向下调整算法

//向下调整
void AdjustDown(HPDataType* 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.2 堆的创建

下面我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算 法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的 子树开始调整，一直调整到根节点的树，就可以调整成堆。

int a[] = {1,5,3,8,7,6}; 


//建堆算法一（从第一个孩子向上调整）
//这种写法的时间复杂度为n*logn
//for (int i = 1; i < len; i++)
//{
//	AdjustUp(a, i);//从第一个孩子向上调整建堆
//}
// 
//建堆算法二（从倒数第一个根向下调整）
//这种写法的时间复杂度为O(N)[更优]
for (int i = (len - 1 - 1) / 2; i >= 0; i--)
{
	AdjustDown(a, len, i);//从倒数第一个根向下调整建堆
}

2.3 建堆时间复杂度

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的 就是近似值，多几个节点不影响最终结果)：

因此：向下调整建堆的时间复杂度为O(N)。 

2.4 堆的插入

先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。

// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	//先判断容量大小是否足够
	if (hp->_size == hp->_capacity)
	{
		int newcapacity = hp->_capacity == 0 ? hp->_capacity = 4 : hp->_capacity * 2;
		//如果原来没有空间，就给上4，有的话就扩大为原来的两倍
		HPDataType* ptr = (HPDataType*)realloc(hp->_a, newcapacity * sizeof(HPDataType));//动态扩容
		if (ptr == NULL)
		{
			perror("realloc fail;");
			return;
		}
		//也可以用assert断言一下
		hp->_a = ptr;//开辟成功将地址传给arr
		hp->_capacity = newcapacity;//更新容量
	}
	//对堆进行插入操作
	hp->_a[hp->_size] = x;
	hp->_size++;
	//插入一个数据后就进行向上调整，保证堆的结构
	AdjustUp( hp->_a,  hp->_size-1);
}

2.5 堆的删除

删除堆是删除堆顶的数据，将堆顶的数据根最后一个数据一换，然后删除数组最后一个数据，再进行向下调 整算法。

// 堆的删除
void HeapPop(Heap* 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.6 完整代码

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;
}Heap;
//堆的初始化
void HeapInit(Heap* hp);

// 堆的销毁
void HeapDestory(Heap* hp);

// 堆的插入
void HeapPush(Heap* hp, HPDataType x);

// 堆的删除
void HeapPop(Heap* hp);

// 取堆顶的数据
HPDataType HeapTop(Heap* hp);

// 堆的数据个数
int HeapSize(Heap* hp);

// 堆的判空
bool HeapEmpty(Heap* hp);

Heap.c 

#include"Heap.h"

//堆的初始化
void HeapInit(Heap* hp)
{
	assert(hp);
	hp->_a = NULL;
	hp->_capacity = hp->_size = 0;
}

// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->_a);
	hp->_a = NULL;
	hp->_capacity = hp->_size = 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(child>0)
	{
		if (a[child] < a[parent])//< 建小堆；> 建大堆
		{
			swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	//先判断容量大小是否足够
	if (hp->_size == hp->_capacity)
	{
		int newcapacity = hp->_capacity == 0 ? hp->_capacity = 4 : hp->_capacity * 2;
		//如果原来没有空间，就给上4，有的话就扩大为原来的两倍
		HPDataType* ptr = (HPDataType*)realloc(hp->_a, newcapacity * sizeof(HPDataType));//动态扩容
		if (ptr == NULL)
		{
			perror("realloc fail;");
			return;
		}
		//也可以用assert断言一下
		hp->_a = ptr;//开辟成功将地址传给arr
		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 + 1] < a[child])//如果右孩子小于左孩子,右孩子与父亲比较
		{
			child++;
		}
		if (a[child] < a[parent])//建小堆，即小的当父亲
		{
			swap(&a[child] , &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}


// 堆的删除
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->_size > 0);
	//先交换根与叶子的位置，保证根的左右都是堆，方便后面的根先下调整
	swap(&hp->_a[0], &hp->_a[hp->_size - 1]);
	//再删除最后一个数据，即是堆的最小或最大值
	hp->_size--;
	AdjustDown(hp->_a, hp->_size, 0);
}

// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(hp->_size > 0);
	return hp->_a[0];
}

// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->_size;
}

// 堆的判空
bool HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->_size == 0;
}

3、完结散花

好了，这期的分享到这里就结束了~

如果这篇博客对你有帮助的话，可以用你们的小手指点一个免费的赞并收藏起来哟~

如果期待博主下期内容的话，可以点点关注，避免找不到我了呢~

我们下期不见不散~~

​​​​

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

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

相关文章

ACM实训第十七天

ACM实训第十七天

Is It A Tree? 问题 考试时应该做不出来&#xff0c;果断放弃 树是一种众所周知的数据结构&#xff0c;它要么是空的(null, void, nothing)&#xff0c;要么是一个或的集合满足以下属性的节点之间有向边连接的节点较多。 •只有一个节点&#xff0c;称为根节点&#xff0c;它…
阅读更多...
【设计模式深度剖析】【2】【创建型】【工厂方法模式】

【设计模式深度剖析】【2】【创建型】【工厂方法模式】

&#x1f448;️上一篇:单例模式 | 下一篇:抽象工厂模式&#x1f449;️ 目录 工厂方法模式概览工厂方法模式的定义英文原话直译 工厂方法模式的4个角色抽象工厂&#xff08;Creator&#xff09;角色具体工厂&#xff08;Concrete Creator&#xff09;角色抽象产品&#x…
阅读更多...
Celery教程

Celery教程

一、什么是Celery 1.1、celery是什么 Celery是一个简单、灵活且可靠的&#xff0c;处理大量消息的分布式系统&#xff0c;专注于实时处理的异步任务队列&#xff0c;同时也支持任务调度。 Celery的架构由三部分组成&#xff0c;消息中间件&#xff08;message broker&#x…
阅读更多...
从零开始学Vue3--环境搭建

从零开始学Vue3--环境搭建

1.搭建环境 下载nodejs nodejs下载地址 更新npm npm install -g npm 设置npm源&#xff0c;加快下载速度 npm config set registry https://registry.npmmirror.com 使用脚手架创建项目 npm create vuelatest 根据你的需要选择对应选项 进入新建的项目下载依赖 npm in…
阅读更多...
大模型时代，掌握Event Stream技术提升Web响应速度

大模型时代，掌握Event Stream技术提升Web响应速度

大模型时代，每天搜索都可能会用到一种或多种大模型，在大文本输出的时候，页面是一字一字，一段一段的慢慢输出出来的，这背后是如何实现的呢？我们以KIMI为例 先抓个请求 我们发现界面展示是一句话，但是接口返回的时候是一个字一个字的。 普通请求 多了Event Stream的处理 …
阅读更多...
机器人非线性控制方法——线性化与解耦

机器人非线性控制方法——线性化与解耦

机器人非线性控制方法是针对具有非线性特性的机器人系统所设计的一系列控制策略。其中&#xff0c;精确线性化控制和反演控制是两种重要的方法。 1. 非线性反馈控制 该控制律采用非线性反馈控制的方法&#xff0c;将控制输入 u 分解为两个部分&#xff1a; α(x): 这是一个与…
阅读更多...
更新web文件40秒后生效

更新web文件40秒后生效

服务器web服务使用的是nginx。 经测试&#xff0c;上传文件后大约40秒后生效。 更新文件不立即生效。 网上资料说根nginx中sendfile选项有关。 在nginx配置文件中&#xff0c;http区域里将sedfile设置为off&#xff0c;重启nginx服务。 谷歌浏览器强制刷新一次&#xff0c;…
阅读更多...
用ControlNet+Inpaint实现stable diffusion模特换衣

用ControlNet+Inpaint实现stable diffusion模特换衣

用ControlNetInpaint实现stable diffusion模特换衣 ControlNet 训练与架构详解ControlNet 的架构用于文本到图像扩散的 ControlNet训练过程Zero卷积层的作用解释 inpaintInpaint Anything 的重要性Inpaint Anything 的功能概述 在现代计算机视觉领域&#xff0c;稳定扩散&#…
阅读更多...
【计算机视觉（3）】

【计算机视觉（3）】

基于Python的OpenCV基础入门——图形与文字的绘制 图形与文字的绘制&#xff1a;画线画矩形画圆画多边形加文字 图形与文字绘制的代码实现&#xff1a; 图形与文字的绘制&#xff1a; 画线 img cv2.line(img, pt1, pt2, color, thickness) 参数&#xff1a; img&#xff1a;…
阅读更多...
Android 构建时：Manifest merger failed : Attribute application@name value

Android 构建时：Manifest merger failed : Attribute application@name value

在AndroidStudio 构建时发现此问题&#xff1a; Manifest merger failed : Attribute applicationname value解决方案&#xff1a;在主Manifest中增加replace <applicationandroid:name".MyApp"android:allowBackup"false"tools:replace"android…
阅读更多...
儿童卧室灯品牌该如何挑选？几款专业儿童卧室灯品牌分享

儿童卧室灯品牌该如何挑选？几款专业儿童卧室灯品牌分享

近视在儿童中愈发普遍&#xff0c;许多家长开始认识到&#xff0c;除了学业成绩之外&#xff0c;孩子的视力健康同样重要。毕竟&#xff0c;学业的落后可以逐渐弥补&#xff0c;而一旦孩子近视&#xff0c;眼镜便可能成为长期伴随。因此&#xff0c;专业的护眼台灯对于每个家庭…
阅读更多...
工作站虚拟化：RTX A5000的图形工作站实现多用户独立运行Siemens NX 设计软件

工作站虚拟化：RTX A5000的图形工作站实现多用户独立运行Siemens NX 设计软件

一、背景 Siemens NX 是由西门子数字工业软件&#xff08;Siemens Digital Industries Software&#xff09;开发的一款先进的集成计算机辅助设计&#xff08;CAD&#xff09;、计算机辅助制造&#xff08;CAM&#xff09;和计算机辅助工程&#xff08;CAE&#xff09;软件。它…
阅读更多...
Python代码实现代价函数

Python代码实现代价函数

最小二乘法 最小二乘法是一种在统计学、数学、工程学和计算机科学等领域广泛使用的优化方法。 基本原理 最小二乘法的主要目的是找到一组模型参数&#xff0c;使得根据这些参数所预测的数据与实际观测数据之间的差异&#xff08;即残差&#xff09;的平方和最小。 数学表达…
阅读更多...
【LeetCode刷题】三数之和、四数之和

【LeetCode刷题】三数之和、四数之和

【LeetCode刷题】Day 6 题目1&#xff1a;LCR 7.三数之和思路分析&#xff1a;思路1&#xff1a;排序暴力枚举set去重思路2&#xff1a;单调性双指针细节处理去重 题目2&#xff1a;18.四数之和思路分析&#xff1a;思路1&#xff1a;排序暴力枚举set去重思路2&#xff1a;单调…
阅读更多...
浅析智能体开发（第二部分）：智能体设计模式和软件架构

浅析智能体开发（第二部分）：智能体设计模式和软件架构

大语言模型&#xff08;LLM&#xff09;驱动的智能体&#xff08;AI Agent&#xff09;展现出许多传统软件所不具备的特征。不仅与传统软件的设计理念、方法、工具和技术栈有显著的差异&#xff0c;AI原生&#xff08;AI Native&#xff09;的智能体还融入了多种新概念和技术。…
阅读更多...
SparkSQL入门

SparkSQL入门

1、SparkSQL是什么&#xff1f; 结论&#xff1a;SparkSQL 是一个即支持 SQL 又支持命令式数据处理的工具 2、SparkSQL 的适用场景&#xff1f; 结论&#xff1a;SparkSQL 适用于处理结构化数据的场景&#xff0c;而Spark 的 RDD 主要用于处理 非结构化数据 和 半结构化数据 …
阅读更多...
【撸源码】【ThreadPoolExecutor】线程池的工作原理深度解析——上篇

【撸源码】【ThreadPoolExecutor】线程池的工作原理深度解析——上篇

1. 前言 线程池这块&#xff0c;作为高频面试题&#xff0c;并且实际使用场景巨多&#xff0c;所以出了这篇文章&#xff0c;一块来研究一下线程池的实现原理&#xff0c;运行机制&#xff0c;从底层深挖&#xff0c;不再局限于面试题。 2. 线程池概览 2.1. 构造器 线程池总…
阅读更多...
Leecode热题100---55：跳跃游戏（贪心算法）

Leecode热题100---55：跳跃游戏（贪心算法）

题目&#xff1a; 给你一个非负整数数组 nums &#xff0c;你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。 判断你是否能够到达最后一个下标&#xff0c;如果可以&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 贪心算…
阅读更多...
数据采集与AI分析，亮数据+通义千问助力跨境电商前行

数据采集与AI分析，亮数据+通义千问助力跨境电商前行

文章目录 前言工具介绍数据采集工具亮数据Web Scraper IDE亮点 AI数据分析工具 实战电商数据采集与AI分析电商平台选取数据采集完全托管数据集自定义数据集 AI分析 价格总结 前言 随着信息技术的飞速发展&#xff0c;数据采集与AI分析在跨境电商中扮演着越来越重要的角色。通过…
阅读更多...
Langchain：数据连接封装、缓存封装和LCEL学习和探索

Langchain：数据连接封装、缓存封装和LCEL学习和探索

&#x1f335; 目录 &#x1f335; &#x1f60b; 数据连接封装 &#x1f354; 文档加载器&#xff1a;Document Loaders 文档处理器&#xff1a;TextSplitter 向量数据库与向量检索 总结 &#x1f349; 缓存封装&#xff1a;Memory &#x1f3d6;️ 对话上下文&#xf…
阅读更多...
最新文章

Copyright @ 2022~2023