[C/C++]数据结构 堆的详解

一:概念

        堆通常是一个可以被看做一棵完全二叉树的数组对象,它是一颗完全二叉树,堆存储的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并且需要满足每个父亲结点总小于其子节点(或者每个父亲结点总大于其子节点)

        堆可以分为两种:

  • 小堆: 任意一个父亲节点都小于其子节点
  • 大堆:任意一个父亲节点都大于其子节点

二:堆的定义

       堆是一个完全二叉树,但是其物理逻辑为数组

typedef int HPDataType;
typedef struct heap
{
	HPDataType* a;
	int size;      
	int capacity;  //数组容量
}HP;

 接口:

//堆的初始化
void InitHeap(HP* hp);

//在堆上入一个数据使其还是堆
void HeapPush(HP* hp, HPDataType x);

//在堆上出一个数据使其还是堆
void HeapPop(HP* hp);

//取堆头元素
HPDataType HeapTop(HP* hp);

//判断堆是否为空
bool HeapEmpty(HP* hp);

//求堆的长度
int HeapSize(HP* hp);

//堆的销毁
void DestoryHeap(HP* hp);

三:接口实现

        堆的实现许多操作和顺序表的实现相同,忘记顺序表的烙铁可以复习一下顺序表-->[C/C++]数据结构----顺序表的实现(增删查改) ,我们以小堆的实现为例:

1.堆的初始化

void InitHeap(HP* hp)
{
	hp->a = NULL;
	hp->size = 0;
	hp->capacity = 0;
}

2.判断堆是否为空

bool HeapEmpty(HP* hp)
{
	assert(hp);
	return hp->size == 0;
}

3.堆的销毁

void DestoryHeap(HP* hp)
{
	assert(hp);
	free(hp->a);
	hp->size = 0;
	hp->capacity = 0;
}

4.返回堆头元素

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

	return hp->a[0];
}

5.堆的大小

int HeapSize(HP* hp)
{
	assert(hp);
	return hp->size;
}

到重点啦!!!

ps:下面的向下和向上调整法都是按小堆实现的,若要按大堆实现只需改下大小比较符号即可

6.入堆(在堆里面插入一个数据,使其还是堆)

      先将数据插入到堆的末尾,如果堆的性质被破坏的话,就让该节点与其父亲结点交换,向上调整,直到满足堆的性质

        例如:在小堆后面插入数据10

由于10小于他的父亲结点,所以应该让10和其父亲结点交换

此时10仍然小于其父亲节点,继续交换

仍然不满足堆的性质,继续交换

向上调整完成

这些数据的存储逻辑上堆为二叉树结构,实际上数据储存在数组中,向上调整法涉及到了如何通过孩子结点找到双亲结点,其实这里有一些结论可以通过一方的下标找到另一方的下标

  • parent = (child-1)/2
  • leftchild = parent*2+1
  • rightchild = parent*2+2

        向上调整法代码实现:

void AdjustUP(HP* hp, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0) //最坏的情况就是需要调整到下标为0的位置
	{
		if (hp->a[parent] > hp->a[child])
		{
			swap(&hp->a[parent], &hp->a[child]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
            //由于插入数据前本来就是堆,如果不满足上述条件,说明所有数据已经满足堆的性质了
			break;
		}
	}
}

入堆:

void HeapPush(HP* hp, HPDataType x)
{
	assert(hp);
    //判断是否需要扩容
	if (hp->size == hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* ret = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (ret == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		hp->a = ret;
		hp->capacity = newcapacity;
	}
    //尾插数据
	hp->a[hp->size] = x;
	hp->size++;
    //向上调整
	AdjustUP(hp, hp->size - 1);
}

7.堆的删除

        堆的删除默认是删除堆顶的元素,如果直接删除堆顶的元素,再将其孩子结点中较小的结点作为堆顶的话,会导致大小关系错乱,因为本来堆顶的左右子树就是堆,按刚刚讲的方法,其堆结构就会被破坏,还需要重新建堆调整,这样的消耗太大了,相反,如果删除一个堆尾的元素消耗却很小,所以可以按如下方法:

  1. 把堆顶元素和堆尾元素交换
  2. 删除堆尾元素
  3. 将堆头元素向下调整到合适位置

向下调整法代码实现:

void AdjustDown(HPDataType* a, int size, int parent)
{
    //这里假设左孩子是两孩子里面较大的
	HPDataType child = parent * 2 + 1;

	while (child<size)
	{    
        //验证假设是否成立,不成立则更新孩子结点
        //右边的条件是为了排除数组访问越界的情况,child+1是右孩子下标
		if (a[child + 1] < a[child] && (child + 1) < size)
		{
			child = child + 1;
		}

        //如果父亲结点比孩子结点大,交换
		if (a[parent] > a[child])
		{
			swap(&a[parent], &a[child]);
			parent = child;
			child = child * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

堆得删除:

void HeapPop(HP* hp)
{
	assert(hp);
	swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;

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

四:效果展示

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 InitHeap(HP* hp);
void HeapPush(HP* hp, HPDataType x);
void HeapPop(HP* hp);
HPDataType HeapTop(HP* hp);
bool HeapEmpty(HP* hp);
int HeapSize(HP* hp);
void DestoryHeap(HP* hp);

heap.c: 用于函数的实现

#define  _CRT_SECURE_NO_WARNINGS 1		
#include"heap.h"

void InitHeap(HP* hp)
{
	hp->a = NULL;
	hp->size = 0;
	hp->capacity = 0;
}

void DestoryHeap(HP* hp)
{
	assert(hp);
	free(hp->a);
	hp->size = 0;
	hp->capacity = 0;
}

void swap(HPDataType* a, HPDataType* b)
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}

void AdjustUP(HP* hp, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (hp->a[parent] > hp->a[child])
		{
			swap(&hp->a[parent], &hp->a[child]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

void HeapPush(HP* hp, HPDataType x)
{
	assert(hp);
	if (hp->size == hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* ret = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (ret == NULL)
		{
			perror("realloc");
			exit(-1);
		}
		hp->a = ret;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;

	AdjustUP(hp, hp->size - 1);
}

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

	return hp->a[0];
}

bool HeapEmpty(HP* hp)
{
	assert(hp);
	return hp->size == 0;
}

int HeapSize(HP* hp)
{
	assert(hp);
	return hp->size;
}

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

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

void HeapPop(HP* hp)
{
	assert(hp);
	swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;

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

test.c :测试功能

#define  _CRT_SECURE_NO_WARNINGS 1		
#include"heap.h"
int main()
{
	int a[] = { 9,8,7,6,5,4,3,2,1 };
	HP hp;
	InitHeap(&hp);
    //这里是将数组的数据依次插入形成堆
	for (int i = 0; i < sizeof(a) / sizeof(int); i++)
	{
		HeapPush(&hp, a[i]);
	}
    
    //依次打印堆头元素
	while (!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
	return 0;
}

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

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

相关文章

C++前缀和算法:统计美丽子字符串

C++前缀和算法:统计美丽子字符串

题目 给你一个字符串 s 和一个正整数 k 。 用 vowels 和 consonants 分别表示字符串中元音字母和辅音字母的数量。 如果某个字符串满足以下条件&#xff0c;则称其为 美丽字符串 &#xff1a; vowels consonants&#xff0c;即元音字母和辅音字母的数量相等。 (vowels * cons…
阅读更多...
大语言模型损失函数详解

大语言模型损失函数详解

我们可以把语言模型分为两类&#xff1a; 自动回归式语言模型&#xff1a;自动回归式语言模型在本质上是单向的&#xff0c;也就是说&#xff0c;它只沿着一个方向阅读句子。正向&#xff08;从左到右&#xff09;预测&#xff1b;反向&#xff08;从右到左&#xff09;预测。…
阅读更多...
Elasticsearch：LangChain 是什么？

Elasticsearch：LangChain 是什么？

当你将应用程序称为 “AI&#xff08;人工智能&#xff09;” 时&#xff0c;这通常意味着它包含与学习模型&#xff08;例如大型语言模型&#xff0c;或 LLM&#xff09;的交互。 [不那么]有趣的事实是&#xff0c;LLM 的使用实际上并不是使应用程序变得智能的原因。 它的特殊…
阅读更多...
Linux中vi常用命令-批量替换

Linux中vi常用命令-批量替换

在日常服务器日志查看中常用到的命令有grep、tail等&#xff0c;有时想查看详细日志&#xff0c;用到vi命令&#xff0c;记录下来&#xff0c;方便查看。 操作文件&#xff1a;test.properites 一、查看与编辑 查看命令&#xff1a;vi 文件名 编辑命令&#xff1a;按键 i&…
阅读更多...
【SAS Planet 下载地图瓦片-读取】

【SAS Planet 下载地图瓦片-读取】

SAS Planet下载地图瓦片请看上一篇 详细介绍了下载方法 【SAS Planet 下载地图瓦片】-CSDN博客 准备工作&#xff1a; 1.提前下载好地图瓦片数据 SAS Planet下载地图瓦片默认存储路径如下 默认存储格式为 .sqlitedb 2.提前准备好 java开发环境和开发工具&#xff0c;新建 一个…
阅读更多...
印度客户来访广东育菁装备考察桌面型数控机床

印度客户来访广东育菁装备考察桌面型数控机床

印度客户来访广东育菁装备考察桌面型数控机床&#xff0c;这是一个重要的商业活动&#xff0c;对于育菁装备来说&#xff0c;这是一个展示产品和技术实力&#xff0c;拓展国际市场的好机会。 在接待印度客户的过程中&#xff0c;育菁装备需要做好充分的准备&#xff0c;包括&am…
阅读更多...
YOLOv8改进 | SAConv可切换空洞卷积（附修改后的C2f+Bottleneck）

YOLOv8改进 | SAConv可切换空洞卷积（附修改后的C2f+Bottleneck）

论文地址&#xff1a;官方论文地址 代码地址&#xff1a;官方代码地址 一、本文介绍 本文给大家带来的改进机制是可切换的空洞卷积&#xff08;Switchable Atrous Convolution, SAC&#xff09;是一种创新的卷积网络机制&#xff0c;专为增强物体检测和分割任务中的特征提取而…
阅读更多...
Linux socket编程(6):IO复用之select原理及例子

Linux socket编程(6):IO复用之select原理及例子

文章目录 1 五种I/O模型1.1 阻塞I/O模型1.2 非阻塞I/O模型1.3 I/O复用模型1.4 信号驱动I/O模型1.5 异步I/O模型 2 select函数3 select实战&#xff1a;实现多个套接字监听3.1 客户端3.2 服务端3.3 实验结果3.4 完整代码 在之前的网络编程中&#xff0c;我们遇到了一个问题&…
阅读更多...
初识数据结构

初识数据结构

归纳编程学习的感悟&#xff0c; 记录奋斗路上的点滴&#xff0c; 希望能帮到一样刻苦的你&#xff01; 如有不足欢迎指正&#xff01; 共同学习交流&#xff01; &#x1f30e;欢迎各位→点赞 &#x1f44d; 收藏⭐ 留言​&#x1f4dd; 熬过了我们不想要的生活&#xf…
阅读更多...
RT-DETR论文阅读笔记（包括YOLO版本训练和官方版本训练）

RT-DETR论文阅读笔记（包括YOLO版本训练和官方版本训练）

论文地址&#xff1a;RT-DETR论文地址 代码地址&#xff1a;RT-DETR官方下载地址 大家如果想看更详细训练、推理、部署、验证等教程可以看我的另一篇博客里面有更详细的介绍 内容回顾&#xff1a;详解RT-DETR网络结构/数据集获取/环境搭建/训练/推理/验证/导出/部署 目录 一…
阅读更多...
【计算机网络笔记】多路访问控制(MAC)协议——轮转访问MAC协议

【计算机网络笔记】多路访问控制(MAC)协议——轮转访问MAC协议

系列文章目录 什么是计算机网络&#xff1f; 什么是网络协议&#xff1f; 计算机网络的结构 数据交换之电路交换 数据交换之报文交换和分组交换 分组交换 vs 电路交换 计算机网络性能&#xff08;1&#xff09;——速率、带宽、延迟 计算机网络性能&#xff08;2&#xff09;…
阅读更多...
HCIA-RS基础-RIP路由协议

HCIA-RS基础-RIP路由协议

前言&#xff1a; RIP路由协议是一种常用的距离矢量路由协议&#xff0c;广泛应用于小规模网络中。本文将详细介绍RIP路由协议的两个版本&#xff1a;RIPv1和RIPv2&#xff0c;并介绍RIP的常用配置命令。通过学习本文&#xff0c;您将能够掌握RIP协议的基本原理、RIPv1和RIPv2的…
阅读更多...
软件工程期末复习（选择+填空+判断）

软件工程期末复习（选择+填空+判断）

文章目录 软件工程期末复习一、 选择题 软件工程期末复习 一、 选择题 1.“软件危机”的表现不包括&#xff1a;&#xff08;c&#xff09; A、软件产品不能按期交付 B、用户对“已完成的”软件产品时常不满意 C、程序员越来越供不应求 D、软件项目难以管理&#xff0c;维护困…
阅读更多...
Java Thread 介绍

Java Thread 介绍

线程是操作系统调度的最小单元, 也叫轻量级进程。它被包含在进程之中, 是进程中的实际运作单位。 同一进程可以创建多个线程, 每个线程都有自己独立的一块内存空间, 并且能够访问共享的内存变量。 1 线程的分类 在 Java 中, 线程可以分为 2 种 守护线程: 守护线程是为用户线程…
阅读更多...
kali linux英文改中文

kali linux英文改中文

如果英语基础较好的同学可以不用调整 反之则需要 找到终端&#xff08;就是输入命令的那个地方 如下&#xff09;点击它出现命令终端 切换为root用户&#xff0c;命令为&#xff1a; sudo dpkg-reconfigure locales 然后回车 找到这个zh_CN 然后回车 鼠标下键选中并且回车 输…
阅读更多...
耶鲁博弈论笔记

耶鲁博弈论笔记

编辑记录&#xff1a; 1126&#xff1a;开个新坑&#xff0c;耶鲁大学的博弈论课程&#xff0c; 和专业相关不大&#xff0c;纯兴趣&#xff0c;尽量写好一点吧 1. 首先指出博弈论是一种研究策略形式的方法&#xff0c;对于经济学中&#xff0c;完全竞争市场只能被动接受均衡…
阅读更多...
IT问题解答类型网站源码

IT问题解答类型网站源码

问答网是一款为IT工程师提供的问答平台&#xff0c;旨在帮助用户在线获取专业知识和相关问题的答案。在问答网&#xff0c;用户可以轻松找到其他人的问答问题&#xff0c;并在这里寻求解答。如果您有任何想要解决的问题&#xff0c;都可以在此发布问题并得到其他同行的解答。 …
阅读更多...
【STL】string类 （下）

【STL】string类 （下）

目录 1&#xff0c;insert 2&#xff0c;erase 3&#xff0c;find 4&#xff0c;replace 5&#xff0c;rfind 6&#xff0c;substr 7&#xff0c;find_first_of 8&#xff0c;find_first_not_of 9&#xff0c;find_last_of 10&#xff0c;operator 11&#xff0c;ge…
阅读更多...
Qt TCP网络上位机的设计（通过网络编程与下位机结合）

Qt TCP网络上位机的设计（通过网络编程与下位机结合）

目录 TCP 协议基础 QTcpServer 和 QAbstractSocket 主要接口函数 TCP 应用程序 1.服务端 2.客户端 上位机通过网络编程与下位机实现通信 TCP 协议基础 传输控制协议&#xff08;TCP&#xff0c;Transmission Control Protocol&#xff09;是一种面向连接的、可靠的、基于…
阅读更多...
Camtasia Studio2024专业的屏幕录制和视频剪辑软件

Camtasia Studio2024专业的屏幕录制和视频剪辑软件

Camtasia2024专业的屏幕录制和视频剪辑软件3000多万专业人士在全球范围内使用Camtasia展示产品&#xff0c;教授课程&#xff0c;培训他人&#xff0c;以更快的速度和更吸引人的方式进行沟通和屏幕分享。使您在Windows和Mac上进行录屏和剪辑创作专业外观的视频变得更为简单。 …
阅读更多...
最新文章

Copyright @ 2022~2023