【数据结构】什么是堆，如何使用无序数组生成一个堆？

文章目录

  • 一、堆的概念及其介绍
  • 二、如何使用无序序列构建一个堆？
  • 三、C语言实现堆的基本操作
    • 结构体创建与销毁
    • 获取堆顶数据与个数及堆的判空
    • 堆的插入与删除
  • 源代码分享

一、堆的概念及其介绍

堆(Heap)是计算机科学中一类特殊的数据结构的统称，堆通常是一个可以被看做一棵完全二叉树的数组对象。如果有一个关键码的集合K = { ， ， ，…， }，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足： <= 且 <= ( >= 且 >= ) i = 0，1， 2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆满足下列性质：

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

    • 每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆
    • 每个结点的值都小于或等于具左石孩子结点 的值，称为小顶堆。

  • 堆总是一棵完全二叉树。

结构图示

在这里插入图片描述

二、如何使用无序序列构建一个堆？

​ 如果有一组无序的数组，{50，10，90，30，70，40，80，60，20}，我们将它抽象为逻辑结构，z这时怎么将无序序列变成一个大堆或者小堆呢？

在这里插入图片描述

向上调整法

​ 从下标为1的位置开始，也就是图中10的位置，依次进行向上调整，每次将更小的换到上面，

题目中有个小问题，如何找到父节点？
在这里插入图片描述

  • 父节点 = （子结点-1）/2
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
typedef int HeapDataType;

void swap(HeapDataType* a, HeapDataType* b)		//交换
{
	HeapDataType temp;
	temp = *a;
	*a = *b;
	*b = temp;
}
void Adjustup(HeapDataType* arr, int child)		//向上调整函数
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[child] < arr[parent])
		{
			swap(&arr[child], &arr[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void CreateHeap(int* a, int n)			//使用无序数组创建堆
{
	for (int i = 1; i < n; i++)
	{
		Adjustup(a, i);
	}
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}

int main()
{
	int arr[] = { 50,10,90,30,70,40,80,60,20 };
	CreateHeap(arr, sizeof(arr) / sizeof(int));
}

向下调整法（更优）

​ 从非叶节点的最后一个数据的下标开始，每次取出孩子中较大或较小的数（看是大堆还是小堆）向下进行调整，由于每多一层，下层是上层的二倍，这种办法直接可以省略掉最后一层，也可以达到建堆的目的，所以这种办法为更优的办法。

由于需要向下调整，所以这种办法需要找到子节点，我们已经知道父结点的运算了，子结点就是父节点的逆运算。

在这里插入图片描述

  • 子节点：父节点*2+1
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <assert.h>
typedef int HeapDataType;

void swap(HeapDataType* a, HeapDataType* b)		//交换
{
	HeapDataType temp;
	temp = *a;
	*a = *b;
	*b = temp;
}
void AdjustDown(HeapDataType* arr, int n, int parent)	//向下调整
{
	assert(arr);
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child<n - 1 && arr[child] > arr[child + 1])
		{
			child = child + 1;
		}
		if (arr[child] < arr[parent])
		{
			swap(&arr[child], &arr[parent]);
		}
		parent = child;
		child = child * 2 + 1;
	}
}
void CreateHeap(int* a, int n)					//使用无序数组创建堆
{
	for (int i = (n - 2) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}

int main()
{
	int arr[] = { 50,10,90,30,70,40,80,60,20 };
	CreateHeap(arr, sizeof(arr) / sizeof(int));
}

三、C语言实现堆的基本操作

结构体创建与销毁

顺序存储方式实现堆采用顺序表进行存储。

typedef int HeapDataType;
typedef struct Heap
{
	HeapDataType* arr;			
	int size;			//当前大小
	int capacity;		//当前容量上限
}Heap;

void HeapDestroy(Heap* ph)
{
	assert(ph);			
	free(ph->arr);
	ph->arr = NULL;
	ph->capacity = 0;
	ph->size = 0;
	free(ph);			//由于顺序表空间是申请堆空间的内存所以需要进行释放
}

获取堆顶数据与个数及堆的判空

HeapDataType HeapTop(Heap* ph) 
{
	assert(ph);
	return ph->arr[0];
}

int HeapSize(Heap* ph)
{
	assert(ph);
	return ph->size;
}

int HeapEmpty(Heap* ph)
{
	assert(ph);
	return ph->size == 0;
}

堆的插入与删除

插入时需要注意空间不足问题，如果空间不足，需要进行二次开辟空间，插入时直接插入到堆尾，然后利用上面写好的向上调整函数。

​ 删除时删掉堆顶数据，将堆底数据拿到堆顶，在进行向下调整，即可保证堆性质不变，依然保持原有的大/小堆。

void HeapPush(Heap* ph, HeapDataType x)
{
	assert(ph);
	if (ph->size == ph->capacity)
	{
		int newcapacity = ph->capacity == 0 ? 5 : ph->capacity * 2;
		HeapDataType* temp = (HeapDataType*)realloc(ph->arr, sizeof(int) * newcapacity);
		if (temp == NULL)
		{
			perror("realloc: error");
			return;
		}
		ph->arr = temp;
		ph->capacity = newcapacity;
	}
	ph->arr[ph->size] = x;
	Adjustup(ph->arr, ph->size - 1);
	ph->size++;
}

void HeapPop(Heap* ph)
{
	assert(ph);
	assert(ph->arr);
	assert(!HeapEmpty(ph));
	swap(&ph->arr[ph->size - 1], &ph->arr[0]);
	ph->size--;
	AdjustDown(ph->arr, ph->size, 0);
}

源代码分享

//heap.h
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <time.h>


typedef int HeapDataType;
typedef struct Heap
{
	int* arr;
	int size;
	int capacity;
}Heap;

void HeapCreate(Heap* ph);
void HeapDestroy(Heap* ph);
void swap(HeapDataType* a, HeapDataType* b);
void Adjustup(HeapDataType* arr, int child);
void AdjustDown(HeapDataType* arr, int n, int parent);
void HeapPush(Heap* ph, HeapDataType x);
void HeapPop(Heap* ph);
HeapDataType HeapTop(Heap* ph);
int HeapSize(Heap* ph);
int HeapEmpty(Heap* ph);

//Heap.c
#include "Heap.h"

void HeapCreate(Heap* ph)
{
	assert(ph);
	ph->arr = NULL;
	ph->capacity = 0;
	ph->size = 0;

}

void HeapDestroy(Heap* ph)
{
	assert(ph);
	free(ph->arr);
	ph->arr = NULL;
	ph->capacity = 0;
	ph->size = 0;
	free(ph);
}

void swap(HeapDataType* a, HeapDataType* b)
{
	HeapDataType temp;
	temp = *a;
	*a = *b;
	*b = temp;
}


void Adjustup(HeapDataType* arr, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (arr[child] < arr[parent])
		{
			swap(&arr[child], &arr[parent]);
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void AdjustDown(HeapDataType* arr, int n, int parent)
{
	assert(arr);
	int child = parent * 2 + 1;
	while(child<n)
	{
		if (child<n-1&&arr[child] > arr[child + 1])
		{
			child = child + 1;
		}
		if (arr[child] < arr[parent])
		{
			swap(&arr[child], &arr[parent]);
		}
		parent = child;
		child = child * 2 + 1;
	}
}

void HeapPush(Heap* ph, HeapDataType x)
{
	assert(ph);
	if (ph->size == ph->capacity)
	{
		int newcapacity = ph->capacity == 0 ? 5 : ph->capacity * 2;
		HeapDataType* temp = (HeapDataType*)realloc(ph->arr, sizeof(int) * newcapacity);
		if (temp == NULL)
		{
			perror("realloc: error");
			return;
		}
		ph->arr = temp;
		ph->capacity = newcapacity;
	}
	ph->arr[ph->size] = x;
	Adjustup(ph->arr, ph->size - 1);
	ph->size++;
}

void HeapPop(Heap* ph)
{
	assert(ph);
	assert(ph->arr);
	assert(!HeapEmpty(ph));
	swap(&ph->arr[ph->size - 1], &ph->arr[0]);
	ph->size--;
	AdjustDown(ph->arr, ph->size, 0);
}

HeapDataType HeapTop(Heap* ph) 
{
	assert(ph);
	return ph->arr[0];
}

int HeapSize(Heap* ph)
{
	assert(ph);
	return ph->size;
}

int HeapEmpty(Heap* ph)
{
	assert(ph);
	return ph->size == 0;
}

//test.c
void CreateHeap(int* a, int n)			//使用向上调整
{
	for (int i = 1; i < n; i++)
	{
		Adjustup(a, i);
	}
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}
void CreateHeap(int* a, int n)		//使用向下调整
{
	for (int i = (n - 2) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
}
int main()
{
	int arr[] = { 50,10,90,30,70,40,80,60,20 };
	CreateHeap(arr, sizeof(arr) / sizeof(int));
}

img

✨本文收录于数据结构理解与实现

当你喜欢一篇文章时，点赞、收藏和关注是最好的支持方式。如果你喜欢我的文章，请不要吝啬你的支持，点赞👍、收藏⭐和关注都是对我最好的鼓励。感谢你们的支持！

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

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

相关文章

公网远程连接Redis数据库【内网穿透】

公网远程连接Redis数据库【内网穿透】

文章目录 1. Linux(centos8)安装redis数据库2. 配置redis数据库3. 内网穿透3.1 安装cpolar内网穿透3.2 创建隧道映射本地端口 4. 配置固定TCP端口地址4.1 保留一个固定tcp地址4.2 配置固定TCP地址4.3 使用固定的tcp地址连接 转发自cpolar内网穿透的文章&#xff1a;公网远程连接…
阅读更多...
docker构建镜像上传到DockerHub

docker构建镜像上传到DockerHub

docker构建镜像上传到DockerHub DockerHub注册账号 DockerHub网址: https://hub.docker.com/ 注册 登录 安装docker docker宿主机环境 centos7 参考网址: https://yeasy.gitbook.io/docker_practice/install/centos 测试 docker 是否安装好 docker -v登录docker 登录 dock…
阅读更多...
Chatgpt版本的opencv安装教程

Chatgpt版本的opencv安装教程

文章目录 前言一、安装opencv方法一二、安装opencv方法二 前言 最近刚买了台RTX 3070的电脑&#xff0c;顺手刷了个ubuntu系统专门玩Carla&#xff0c;为了方便查资料&#xff0c;也顺手搭了浏览chatgpt的环境&#xff0c;用的clash&#xff0c;还挺好用的。然后刚好在看Carla…
阅读更多...
如何使用JQuery实现Js二级联动和三级联动

如何使用JQuery实现Js二级联动和三级联动

前言&#xff1a;使用JQuery封装好的js方法来实现二级三级联动要比直接使用js来实现二级三级联动要简洁很多。所以说JQuery是个非常强大的、简单易用的、兼容性好的JavaScript库&#xff0c;已经成为前端开发人员不可缺少的一部分&#xff0c;是Web开发中最流行的JavaScript库之…
阅读更多...
Mysql数据库对表的基本操作

Mysql数据库对表的基本操作

一.表基本操作 1.当前数据库内创建表 2.查看表 3.删除表 4.修改表结构 5.复制表&#xff08;结构&#xff09; 二.表约束创建 1.约束的作用 2.约束的类型 3.演示 一.表基本操作 1.当前数据库内创建表 CREATE TABLE 表名( 列名 列数据类型&#xff0c; 列名 列…
阅读更多...
小兔鲜--项目总结3

小兔鲜--项目总结3

目录 结算模块-地址切换交互实现 地址切换交互需求分析 打开弹框交互实现 地址激活交互实现 订单模块-生成订单功能实现 支付模块-实现支付功能 支付业务流程 支付模块-支付结果展示 支付模块-封装倒计时函数 理解需求 实现思路分析 会员中心-个人中心信息渲染 分页…
阅读更多...
solr快速上手：managed-schema标签详解（三）

solr快速上手：managed-schema标签详解（三）

0. 引言 core核心是solr中的重中之重&#xff0c;类似数据库中的表&#xff0c;在搜索引擎中也叫做索引&#xff0c;在solr中索引的建立&#xff0c;要先创建基础的数据结构&#xff0c;即schema的相关配置&#xff0c;今天继续来学习solr的核心知识&#xff1a; solr快速上手…
阅读更多...
OpenCV——最小外接矩形

OpenCV——最小外接矩形

目录 一、主要函数二、代码实现三、结果展示 一、主要函数 cv::RotatedRect cv::minAreaRect(const cv::Mat& points );emspminAreaRect 函数用于计算给定点集的最小外接矩形。该矩形的长和宽是可以任意旋转的&#xff0c;因此被称为旋转矩形。 points &#xff1a;是一个…
阅读更多...
article-码垛机器人admas仿真

article-码垛机器人admas仿真

按照运动学仿真的类似步骤为机器人添加材料、运动副和关节驱动&#xff0c;给机器人手腕末端施加50N最大负载&#xff0c;仿真模型如图5-17。 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AXYQVZPq-1684936426972)(data:image/svgxml;utf8, )] 图…
阅读更多...
Python实现ACO蚁群优化算法优化BP神经网络回归模型(BP神经网络回归算法)项目实战

Python实现ACO蚁群优化算法优化BP神经网络回归模型(BP神经网络回归算法)项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档视频讲解&#xff09;&#xff0c;如需数据代码文档视频讲解可以直接到文章最后获取。 1.项目背景 蚁群优化算法(Ant Colony Optimization, ACO)是一种源于大自然生物世界的新的仿生进化算法&#xff0c…
阅读更多...
Qt自定义的ColorDialog--仿QColorDialog

Qt自定义的ColorDialog--仿QColorDialog

Qt已经有了色板选择&#xff0c;但是它使用QDialog形成的&#xff0c;每次调用基本上都成了点一个按钮&#xff0c;谈一个模态框&#xff0c;选择好颜色之后再关掉模态框。 但是&#xff0c;如果想将颜色选择板放在窗口上&#xff0c;并不会有模态的功能就会比较麻烦&#xff…
阅读更多...
docker安装mysql8.0.33

docker安装mysql8.0.33

1 从docker仓库中拉去mysql 8.0 docker pull mysql:8.0如果使用 docker pull mysql 默认拉取的是最新版本的mysql 上面我拉去的是8.0的版本&#xff0c;最后拉取过来的是8.0.33 如果有想要指定的版本&#xff0c;可以直接写指定版本&#xff0c;如&#xff1a; docker pull my…
阅读更多...
pytorch：nn.ModuleList和nn.Sequential、list的用法以及区别

pytorch：nn.ModuleList和nn.Sequential、list的用法以及区别

文章目录 在构建网络的时候&#xff0c;pytorch有一些基础概念很重要&#xff0c;比如nn.Module&#xff0c;nn.ModuleList&#xff0c;nn.Sequential&#xff0c;这些类我们称为为容器&#xff08;containers&#xff09;&#xff0c;可参考containers。本文中我们主要学习nn.…
阅读更多...
【Python】正则表达式应用

【Python】正则表达式应用

知识目录 一、写在前面✨二、姓名检查三、解析电影排行榜四、总结撒花&#x1f60a; 一、写在前面✨ 大家好&#xff01;我是初心&#xff0c;希望我们一路走来能坚守初心&#xff01; 今天跟大家分享的文章是 正则表达式的应用 &#xff0c;希望能帮助到大家&#xff01;本篇…
阅读更多...
把字节大佬花3个月时间整理的软件测试面经偷偷给室友，差点被他开除了···

把字节大佬花3个月时间整理的软件测试面经偷偷给室友，差点被他开除了···

写在前面 “这份软件测试面经看起来不错&#xff0c;等会一起发给他吧”&#xff0c;我看着面前的面试笔记自言自语道。 就在这时&#xff0c;背后传来了leder“阴森森”的声音&#xff1a;“不错吧&#xff0c;我可是足足花了三个月整理的” 始末 刚入职字节的我收到了大学室…
阅读更多...
Windows 10 X64 内核对象句柄表解析

Windows 10 X64 内核对象句柄表解析

fweWindows 很多API函数都会创建和使用句柄(传入参数)&#xff0c;句柄代表一个内核对象的内存地址&#xff0c;每个进程都有一个句柄表&#xff0c;它保存着进程拥有的句柄&#xff0c;内核也有一个句柄表 PspCidTable&#xff0c;它保存着整个系统的句柄。 ExpLookupHandleTa…
阅读更多...
DNS风险分析及安全防护研究（一）：DNS自身风险分析（中科三方）

DNS风险分析及安全防护研究（一）：DNS自身风险分析（中科三方）

作为互联网上的一项基础服务&#xff0c;DNS在网站运行中起到了至关重要的作用&#xff0c;然而其安全性在很长一段时间内都没有得到足够的重视。DNS采用不可靠的UDP协议&#xff0c;安全性具有较大的漏洞&#xff0c;攻击者很容易利用这些漏洞发动攻击&#xff0c;从而引起一些…
阅读更多...
华为设备这14个广域网命令，值得每位做广域网业务的网工收藏！

华为设备这14个广域网命令，值得每位做广域网业务的网工收藏！

你好&#xff0c;这里是网络技术联盟站。 华为设备广域网命令是网络管理员在运维过程中常用的一类命令。该命令集涵盖了DCC配置命令、PPP配置命令、MP配置命令、PPPoE命令、ATM配置命令、帧中继配置命令、HDLC配置命令、LAPB配置命令、X.25配置命令、IP-Trunk配置命令、ISDN配…
阅读更多...
Java 与数据结构（6）：快速排序

Java 与数据结构（6）：快速排序

ChatGPT 中文指南(大全) 内容包含&#xff1a;如何开通chatgpt、chatgpt的同类站点、prompts 、AI绘图、ChatGPT 工具、相关报告论文、ChatGPT应用项目等 链接&#xff1a;ChatGPT 中文指南(大全) 指令指南&#xff0c;精选资源清单&#xff0c;更好的使用 chatGPT 让你的生产力…
阅读更多...
详解如何使用LAMP架构搭建论坛

详解如何使用LAMP架构搭建论坛

文章目录 1.LAMP概述2.编译安装Apache httpd服务1.关闭防火墙&#xff0c;将安装Apache所需软件包传到/opt目录下2.安装环境依赖包 3.配置软件模块4.编译及安装5.优化配置文件路径&#xff0c;并把httpd服务的可执行程序文件放入路径环境变量的目录中便于系统识别6.添加httpd系…
阅读更多...
最新文章

Copyright @ 2022~2023