[数据结构]堆

一、堆是什么？

堆是一种完全二叉树

完全二叉树的定义：完全二叉树的形式是指除了最后一层之外，其他所有层的结点都是满的，而最后一层的所有结点都靠左边。​​​​​​，从左到右连续。

教材上定义如下:

若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边，这就是完全二叉树。

二、堆

堆分为大堆和小堆

大堆：对于任意一个父结点来说，其子结点的值都小于这个父节点。也就是（父亲>儿子）

小堆:   对于任意一个父结点来说，其子结点的值都大于这个父节点。也就是（父亲<儿子）

所以对堆插入数据时,我们要调整堆,我们可能会发现,导入数据后会出现一种特殊的现象,父子的位置互换了,父亲成为了儿子,儿子成为了父亲,甚至可能影响了祖先。

父子存储关系：

leftchild=parent*2+1

rightchild=parent*2+2

parent=(child-1)/2

三、堆的调整

1.向上调整

字面意思从下往上进行数据的调整，举个例子，假设我这里有个小堆：

假设我们这里在堆插入一个60：

我们会发现符合小堆的定义。

那么，我们要是插入一个30呢？

我们根据小堆的定义我们需要把30与32 的位置对调，如上图。

那么，如果我们插入的是5呢？

我们会发现5比32小，他们的位置交换，5比10还小，所以5和10的位置也交换，过程如上图。

最后这个堆就是这样的：

下面是代码实现：

typedef int HPDataType;//定义堆的数据类型
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap;//堆
void Adjustup(HPDataType* a, HPDataType child)//传入堆的指针和孩子的下标
{
	int parent = (child - 1) / 2;//通过公式算出父亲的下标
	while (child > 0)//设计循环条件,因本质为数组,所以下标大于0,且孩子下标如果是0,则孩子为祖先
	{
		if (a[child] < a[parent])//判断父与子大小
		{
			swap(&a[child], &a[parent]);//交换父子的位置的值
			child = parent;//求出此时交换后原来孩子的下标,便于与新父亲比较
			parent = (parent - 1) / 2;//通过新的儿子的下标求出父亲的下标,便于下一次判断
		}
		else
		{
			break;//退出
		}
	}
}
void swap(HPDataType* a, HPDataType* b)//交换数值的函数
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}

2.向下调整

字面意思，就是从上到下调整，这时有人说这样插入新数值时，用这个好麻烦啊，确实是这样的，向下调整，我们一般可以用于已经存在的数组来建堆。

下面我们来举个例子，我们拥有以下数组：

{50，100，23，45，67，77}，我们要把他们建立成小堆

建立成堆的逻辑结构：

我们从50开始对其判断

看到这里，可能会有疑惑，为什么100>77同时100>67,交换的是100和67，因为如果77和100交换之后继续比较我们会发现67<77，所以上图是对的

因此我们可以得到的堆最后、如下：

思考一下这样对吗？

下面我们来用代码实现：

//建立堆,堆的数据类型,交换数值函数省略
void Adjustdown(HPDataType* a, int n, int parent)//传入堆中位置的指针,传入堆的最后一位下标和开
{                                                //始的父亲下标
	int child = parent * 2 + 1;//算出孩子下标
	while (child < n)//构建循环条件
	{
		if (child + 1 < n && a[child + 1] < a[child])//如果孩子没到最后同时右孩子小于左孩子
		{
			++child;//最小的孩子为右孩子
		}
		if (a[child] < a[parent])//孩子和父亲比较
		{
			swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

将这些搞懂了,我们就能尝试去手搓一个堆了

四、手搓堆

 知道这些我们可以尝试自己来手搓一个堆了，假设我们来手搓一个大堆，顺便实现相应的操作。

1.堆的结构体和数据类型

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

2.堆的初始化

void HeapInit(Heap* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->capacity = 0;
	hp->size = 0;
}

3.对堆的空间判断和扩容

我们知道堆的物理结构数组，我们可以联想到顺序表，我们需要动态开辟空间，所以需要在插入新数据时，对现有的空间进行判断。

void AddHeap(Heap* hp)
{
	int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
	HPDataType* temp = realloc(hp->a, sizeof(HPDataType) * newcapacity);
	if (temp==NULL)
	{
		perror("realloc fail");
		return;
	}
	hp->a = temp;
	hp->capacity = newcapacity;
}

4.在堆尾部插入数据

如果我们在队尾差尾一个数据，根据对的定义我们需要建堆进行调整，前面我们说过这里适合用向上调整。

void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if(hp->size==hp->capacity)
	{
		AddHeap(hp);
	}
	hp->a[hp->size] = x;
	hp->size++;
	Adjustup(hp->a, hp->size - 1);
}

void Adjustup(HPDataType* a, HPDataType 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;
		}
	}
}

5.在堆头删除数据

删除堆头数据一样会使本来的关系改变，所以我们需要堆数据的位置进行调整，因为我们改变的时头，所以我们这里使用向下调整比较好。

void Adjustup(HPDataType* a, HPDataType 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 HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->a);
	swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
	Adjustdown(hp->a, hp->size, 0);
}

6.获取堆顶的数据，判断是否为空，获取数据个数

这个比较简单我直接上代码了

HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(hp->a);
	return hp->a[0];
}
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->size;
}
int HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->size == 0;
}

7.堆的销毁

动态内存开辟的空间要释放

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

8.总体代码

//Heap.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int HPDataType;
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap;

//堆的初始化
void HeapInit(Heap* hp);
// 堆的构建
//void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的销毁
void HeapDestory(Heap* hp);
// 堆的插入
void HeapPush(Heap* hp, HPDataType x);
// 堆的删除
void HeapPop(Heap* hp);
// 取堆顶的数据
HPDataType HeapTop(Heap* hp);
// 堆的数据个数
int HeapSize(Heap* hp);
// 堆的判空
int HeapEmpty(Heap* hp);
//Heap.c

#include"Heap.h"
void HeapInit(Heap* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->capacity = 0;
	hp->size = 0;
}
void AddHeap(Heap* hp)
{
	int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
	HPDataType* temp = realloc(hp->a, sizeof(HPDataType) * newcapacity);
	if (temp==NULL)
	{
		perror("realloc fail");
		return;
	}
	hp->a = temp;
	hp->capacity = newcapacity;
}
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->capacity = 0;
	hp->size = 0;
}
void swap(HPDataType* a, HPDataType* b)
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}

void Adjustup(HPDataType* a, HPDataType 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 Adjustdown(HPDataType* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && 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 HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if(hp->size==hp->capacity)
	{
		AddHeap(hp);
	}
	hp->a[hp->size] = x;
	hp->size++;
	Adjustup(hp->a, hp->size - 1);
}
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->a);
	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->a);
	return hp->a[0];
}
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->size;
}
int HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->size == 0;
}

最后我们来测试一下这些功能

//test.c


#include<stdio.h>
#include"Heap.h"
int main()
{
	int a[] = { 50,100,70,65,60,32 };
	Heap hp;
	HeapInit(&hp);
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HeapPush(&hp, a[i]);
	}

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

感谢阅读!

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

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

相关文章

AI检测识别技术，为智能化视频生产赋能

AI检测识别技术，为智能化视频生产赋能

在科技飞速发展的今天&#xff0c;智能化生产已经成为企业提高效率、降低成本、增强竞争力的关键所在。美摄科技&#xff0c;作为一家在音视频处理技术领域保持领先的创新型企业&#xff0c;不仅致力于提供卓越的音视频处理技术&#xff0c;更在AI检测识别领域积累了深厚的实力…
阅读更多...
机器视觉相关硬件

机器视觉相关硬件

机器视觉相关硬件 完整的图像采集系统一般包括相机、镜头、图像采集卡、光源等。硬件的选型将关系到图像的质量和传输的速率&#xff0c;也会间接影响视觉软件算法的工作效率。硬件和软件需要配合得当&#xff0c;彼此互补。本文将介绍机器视觉的4个主要硬件的选型。 一、相机…
阅读更多...
【日常记录】【插件】使用ColorThief,跟随图片变化改变网页背景

【日常记录】【插件】使用ColorThief,跟随图片变化改变网页背景

文章目录 1、效果图2、ColorThief3、实现4、参考链接 1、效果图 想要实现,界面的背景颜色,跟随图片的 颜色来进行展示, 2、ColorThief 要想实现跟随图片变化实现网页背景渐变效果&#xff0c;则需要获取图片的主要颜色&#xff0c;可以使用ColorThief库来获取图片的颜色 需要注…
阅读更多...
你真的会做抖音小店吗？你做抖店的方法是正确的吗？教学分享

你真的会做抖音小店吗？你做抖店的方法是正确的吗？教学分享

大家好&#xff0c;我是电商花花。 新的一年&#xff0c;不少做抖店的商家都会产生一个疑问&#xff0c;2024年抖音小店无货源还能继续做吗&#xff1f; 做无货源模式还会被处罚吗&#xff1f; 先说答案&#xff0c;2024年抖音小店无货源能做&#xff0c;不仅能做且仍然是抖音…
阅读更多...
Java学习笔记（14）

Java学习笔记（14）

常用API Java已经写好的各种功能的java类 Math Final修饰&#xff0c;不能被继承 因为是静态static的&#xff0c;所以使用方法不用创建对象&#xff0c;使用里面的方法直接 math.方法名 就行 常用方法 Abs,ceil,floor,round,max,minm,pow,sqrt,cbrt,random Abs要注意参数的…
阅读更多...
电商评论数据聚类实验报告

电商评论数据聚类实验报告

目录 实验目的整体思路数据介绍代码与实验步骤 4.1 爬虫代码 4.2 数据清洗 4.3 分词 4.4 去停用词 4.5 计算TF-IDF词频与聚类算法应用 4.6 生成词云图实验结果 5.1 词云图 5.2 聚类结果分析不足与反思参考资料 1. 实验目的 掌握无监督学习问题的一般解决思路和具体解决办法&…
阅读更多...
讯鹏智能边缘计算网关主机，支持MQTT协议主动上传上位机软件平台

讯鹏智能边缘计算网关主机，支持MQTT协议主动上传上位机软件平台

随着科技的不断发展&#xff0c;智能化设备在我们的生活中扮演着越来越重要的角色。而智能边缘计算网关作为连接智能设备与互联网的重要纽带&#xff0c;其远程运维功能为管理者带来了极大的便利。特别是像OkEdge边缘计算网关这样的产品&#xff0c;不仅可以替代传统的Windows系…
阅读更多...
Unity中使用AVPro Video播放视频的完全指南

Unity中使用AVPro Video播放视频的完全指南

Unity AVPro是一款强大的视频播放解决方案&#xff0c;它支持多种视频格式和编解码器&#xff0c;能够在Unity中实现高质量的视频播放。本教程将指导你如何在Unity项目中使用AVPro播放视频。 目录如下 1、安装AVPro Video2、在UI上显示视频3、在3D物体上显示视频&#xff0c;…
阅读更多...
JWT（跨域身份验证解决方案）

JWT（跨域身份验证解决方案）

Json web token (JWT), 跨域身份验证解决方案，特别适用于分布式站点的单点登录（SSO）场景。JWT的声明一般被用来在身份提供者和服务提供者间传递被认证的用户身份信息，以便于从资源服务器获取资源，也可以增加一些额外的其它业务逻辑所必须的声明信息，该token也可直接被用于…
阅读更多...
jQuery 常用API

jQuery 常用API

一、jQuery 选择器 1.1 jQuery 基础选择器 原生 JS 获取元素方式很多&#xff0c;很杂&#xff0c;而且兼容性情况不一致&#xff0c;因此 jQuery 给我们做了封装&#xff0c;使获取元素统一标准。 1.2 jQuery 层级选择器 jQuery 设置样式 1.3 隐式迭代&#xff08;重要&…
阅读更多...
算法打卡day21|回溯法篇01|理论知识，Leetcode 77.组合

算法打卡day21|回溯法篇01|理论知识，Leetcode 77.组合

回溯法理论知识 回溯法也可以叫做回溯搜索法&#xff0c;它是一种搜索的方式。回溯是递归的副产品&#xff0c;只要有递归就会有回溯。所以回溯函数也就是递归函数&#xff0c;指的都是一个函数。 回溯法的效率 回溯法并不是什么高效的算法。因为回溯的本质是穷举&#xff0c;…
阅读更多...
打靶记录（个人学习笔记）

打靶记录（个人学习笔记）

一、信息收集 1、主机发现 通过nmap对此网段进行扫描&#xff0c;可以确定靶机ip为192.168.189.144 2、端口扫描 确定了靶机ip之后&#xff0c;我们来扫描端口 发现80端口开放&#xff0c;先访问80端口 用插件识别出一些信息 Wappalyzer插件获得信息&#xff1a;Web服务&am…
阅读更多...
jquery 列表框可以手动修改(调用接口修改)

jquery 列表框可以手动修改(调用接口修改)

类似于这种 直接上代码 列表框 <td>//目的主要是获取属性名的(要更改的属性名) 在下面juqery的这一行(var field $(thisobj).prev(input).attr(name);)有体现<input type"hidden" name"voyage" value"${M_PSI_PERIOD_INFO.port}">…
阅读更多...
卓越巨人wzy

卓越巨人wzy

解法&#xff1a; 向下取整同理&#xff0c;f(n)20230416-n 当n20230416时&#xff0c;f&#xff08;n&#xff09;0&#xff0c;之后由于向上取整&#xff0c;结果恒为0. #include<iostream> #include<algorithm> #include<vector> using namespace std; …
阅读更多...
关系型数据库mysql（1）基础认知和安装

关系型数据库mysql（1）基础认知和安装

目录 一.数据库的基本概念 1.1数据 1.2表 1.3数据库 1.4 DBMS 数据库管理系统 1.4.1基本功能 1.4.2优点 1.4.3DBMS的工作模式 二.数据库的发展历史 2.1发展的三个阶段 第一代数据库 第二代数据库 第三代数据库 2.2mysql发展历史 三.主流数据库 四.关系型数据库和…
阅读更多...
Windows三大认证！ NTLM_Relay攻击

Windows三大认证！ NTLM_Relay攻击

Windows有三大认证 NTLM本地认证NTLM网络认证Kerberos域认证 1.Kerberos域认证 对于Kerberos域认证&#xff0c;我之前讲过很多的文章 所以这里就不再赘述了 2.NTLM本地认证 其实就是windows本地登录认证&#xff0c;我之前也讲过&#xff0c;于是也不再赘述了 hhh&#x…
阅读更多...
【Lexus】Executive Sedan

【Lexus】Executive Sedan

文章目录 【基础信息】车漆颜色历年指导价2.5L车型保养 【缺点】混动车型缺点负面 【对比】ES200 vs ES200 龙年限定ES200 vs ES260ES200 vs ES300hES200 vs NX260ES200 vs BMW 325i M 运动曜夜 【Buy】【尺寸】 【基础信息】 丰田&#xff0c;雷克萨斯&#xff0c;1997推出第…
阅读更多...
android studio 安装lombok插件

android studio 安装lombok插件

android studio 安装lombok插件 由于 AS 不是基于 IDEA release 版本进行开发的&#xff0c;因此lombok对idea的插件可能再as中无法查看到。因此再as中通过plugins管理无法安装lombok插件。这就导致再gradle引入lombok后&#xff0c;虽然编译可能会通过&#xff0c;但是代码在查…
阅读更多...
分布式接口幂等性解析

分布式接口幂等性解析

一、概述 幂等性定义&#xff1a;用户对于同一操作发起的一次请求或者多次请求的结果是一致的&#xff0c;不会因为多次点击而产生了副作用。【同一操作指的是同一个浏览器&#xff0c;发送相同的请求】。 常见场景&#xff1a; 提交订单接口。返回提交结果时网络出现故障&am…
阅读更多...
电子元器件行业发展势头强劲，钧崴电子IPO上市抢占市场份额

电子元器件行业发展势头强劲，钧崴电子IPO上市抢占市场份额

电子元器件处于电子信息产业链上游&#xff0c;是通信、计算机及网络、数字音视频等系统和终端产品发展的基础&#xff0c;对电子信息产业的发展起着至关重要的作用。近年来中国电子工业持续高速增长&#xff0c;带动电子元器件产业强劲发展。目前&#xff0c;我国许多门类的电…
阅读更多...
最新文章

Copyright @ 2022~2023