【C语言】数据结构#实现堆

目录

（一）堆

（1）堆区与数据结构的堆

（二）头文件

（三）功能实现

 （1）堆的初始化

（2）堆的销毁

（3）插入数据

（4）删除堆顶的数据        

（5）得到堆顶的数据

（6）判断堆是否为空

（7）得到堆内数据个数

正文开始：

（一）堆

（1）堆区与数据结构的堆

          堆区和数据结构中的堆是两个不同的概念。

       

  1. 堆区 (Heap) ：堆区是计算机内存中的一部分，用于存储动态分配的内存空间。在程序运行时，堆区用于存储使用 new 或 malloc 等方法分配的内存空间，在程序运行结束后，由程序员手动释放。堆区是一块较大的内存区域，用于存储动态分配的数据。堆区的大小可以动态增长或缩小，具有较高的灵活性。堆区的访问速度较慢，但能够存储较大的数据。

  2. 数据结构中的堆：在数据结构中，堆是一种特殊的树状结构，具有以下特点：

  • 堆是一个完全二叉树，即除了最底层外，其他层都是满的，最底层的结点从左到右连续排列。
  • 堆中的每个结点的值都大于等于（或小于等于）其子结点的值，根结点是树中最大（或最小）的结点。
  • 堆可以分为最大堆和最小堆，最大堆的根结点是整个堆中最大的元素，最小堆的根结点是整个堆中最小的元素。

        

         在数据结构中，堆通常用于实现优先队列（Priority Queue）和堆排序（Heap Sort）等算法。堆的插入和删除操作的时间复杂度都为 O(log n)，其中 n 是堆中元素的个数。

（二）头文件

        STL（Standard Template Library）是C++标准库中的一个组件，提供了一系列的通用数据结构和算法，以及一些函数模板，用于简化C++程序的开发。STL包括了容器（Containers）、算法（Algorithms）和迭代器（Iterators）三个主要部分。

  1. 容器（Containers）：STL提供了多种容器，包括向量（vector）、链表（list）、双端队列（deque）、集合（set）、映射（map）等。这些容器提供了不同的数据结构和操作，方便了数据的存储和处理。

  2. 算法（Algorithms）：STL提供了一系列的算法，包括排序、查找、合并、变序、计数等等。这些算法可以对容器中的元素进行操作，使得程序更加高效和简洁。

  3. 迭代器（Iterators）：STL的迭代器是一个泛型指针，用于遍历容器中的元素。迭代器提供了一种统一的访问容器元素的方式，使得算法可以独立于容器而使用。

        本文根据Cpp的STL来实现堆的功能，包括堆的初始化，销毁，插入数据，删除堆顶的数据，得到堆顶的数据，判断堆是否为空，得到堆内数据个数等七个功能接口。

        本文基于顺序表实现堆；

        这里不加解释的给出头文件，根据头文件实现堆的功能：

        命名：Heap.h

#pragma once

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef int HPDatatype;

typedef struct Heap
{
	HPDatatype* a;//存储数据的数组
	int size;     //堆内数据的个数
	int capacity; //顺序表的容量
}HP;

//初始化
void HPinit(HP* php);

//销毁
void HPDestroy(HP* php);

//插入数据
void HPpush(HP* php, HPDatatype x);

//删除数据，规定删除堆顶的数据
void HPpop(HP* php);

//得到堆顶数据
HPDatatype HPtop(HP* php);

//判空
bool HPempty(HP* php);

//数据个数
int HPsize(HP* php);

         

（三）功能实现

 （1）堆的初始化

堆的初始化

        首先，函数接收的指针（被传入的地址）不为空（否则无法进行解引用操作），通过assert断言实现；

        将数组置空，顺序表的大小与容量置0；


//初始化
void HPinit(HP* php)
{
	assert(php);

	php->a = NULL;
	php->capacity = php->size = 0;
}

 

（2）堆的销毁

堆的销毁

          首先，函数接收的指针（被传入的地址）不为空（否则无法进行解引用操作），通过assert断言实现；

        释放掉动态申请的顺序表内的数组，顺序表的大小与容量置0；


//销毁
void HPDestroy(HP* php)
{
	assert(php);

	free(php->a);
	php->capacity = php->size = 0;

}

 

（3）插入数据

 

插入数据

         首先，函数接收的指针（被传入的地址）不为空（否则无法进行解引用操作），通过assert断言实现；

        其次判断数组内数据是否满了

        ——如果顺序表容量等于数组的大小，代表数据满了，那么进行扩容。Newcapacity的赋值通过三目操作符实现：如果capacity为初始值0，Newcapacity赋值为4，否则赋值为2*capacity。如果realloc申请失败，打印错误信息并返回。若申请成功，压入数据。

        ——如果数据没有满，直接在数组中插入数据，由于插入的数据不一定与原数据成堆，所以要进行向上调整；

        调整需要交换，于是提前给出交换的功能接口：

 交换

//传址交换
void Swap(HPDatatype* p1, HPDatatype* p2)
{
	HPDatatype tem = *p1;
	*p1 = *p2;
	*p2 = tem;
}

 

 什么是向上调整？

         堆在逻辑上是二叉树，在物理上实际上是数组，数组的下标如下：

         在堆中，有一个规律：

  •         父节点下标 = （子节点下标 - 1） / 2；
  •         左子节点下标 = （父结点下标  * 2） + 1；
  •         右子节点下标 = （父结点下标  * 2） + 2；

        于是，我们可以通过一个节点的下标，找到他的父和子的下标 ；

本文以实现小堆为例 

向上调整

        将新插入的节点与其父节点比较，如果新节点小于父结点，两节点交换值，继续迭代进行；

         直到新节点的值大于等于父结点，或者已经比到了根节点才停止；


//push实现小堆的向上调整
void AdgustUP(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 HPpush(HP* php, HPDatatype x)
{
	assert(php);
	//数据满，realloc扩容,得到新的大容量顺序表
	if (php->capacity == php->size)
	{
		int Newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDatatype* tem = (HPDatatype*)realloc(php->a, Newcapacity * sizeof(HPDatatype));
		if (tem == NULL)
		{
			perror("realloc fail!");
			return;
		}
		php->a = tem;
		php->capacity = Newcapacity;
	}

	//数据不满，直接插入
	php->a[php->size] = x;
	php->size++;

	//向上调整
	AdgustUP(php->a,php->size-1);
}

 

（4）删除堆顶的数据        

删除数据

        删除数据规定的是删除堆顶的数据；

        函数接收的指针（被传入的地址）不为空（否则无法进行解引用操作），通过assert断言实现；

        如何删除？

        -直接删除，由于二叉树的兄弟节点是没有大小关系的，如果直接删除根节点，那么所有节点的下标减一，这意味着原来的的二叉树的结构就被完全破坏了，接下来只能重新建堆，代价太大。

        -先交换堆顶与最后一个数据，然后删除最后一个数据（其实就是原堆顶数据），然后进行向下调整；

        这样既没有完全破换二叉树的结构，只有一个数据需要调整位置，又操作简便只需size--即可。

向下调整

        思路与向上调整基本一致；


//小堆向下调整——找小
void AdgustDown(HPDatatype* a, int n, int parent)
{
	//假设左孩子小
	int child = parent * 2 + 1;
	while (child < n)
	{
		//如果右孩子小，假设不成立
		if (child + 1 < n && a[child] > a[child + 1])
		{
			child++;
		}
		//此时，child表示较小的孩子
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}

	}

}

删除数据


//删除数据，规定删除堆顶的数据
void HPpop(HP* php)
{
	assert(php);
	//交换堆顶与最后一个数据
	Swap(&php->a[0], &php->a[php->size - 1]);
	//删除堆顶的数据
	php->size--;
	//向下调整
	AdgustDown(php->a, php->size,0);

}

（5）得到堆顶的数据

          首先，函数接收的指针（被传入的地址）不为空（否则无法进行解引用操作），通过assert断言实现；

        其次，堆不为空，通过assert断言实现；

        直接返回堆顶的数据即可；


//得到堆顶数据
HPDatatype HPtop(HP* php)
{
	assert(php);
	assert(!HPempty(php));

	return php->a[0];
}

 

（6）判断堆是否为空

         首先，函数接收的指针（被传入的地址）不为空（否则无法进行解引用操作），通过assert断言实现；

         直接返回判断表达式的值即可；（若为空，返回真（1）；否则返回假（0））

//判空
bool HPempty(HP* php)
{
	assert(php);
	return php->size == 0;
}

 

（7）得到堆内数据个数

          首先，函数接收的指针（被传入的地址）不为空（否则无法进行解引用操作），通过assert断言实现；

        直接返回堆内数据个数即可；


//数据个数
int HPsize(HP* php)
{
	assert(php);

	return php->size;
}

完~

未经作者同意禁止转载 

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

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

相关文章

java中stream流中的concat合并操作

java中stream流中的concat合并操作

可以用stream.of来合并两个流 public class Test7concat {public static void main(String[] args) {/*Stream流:static <T> Stream<T> concat(Stream<? extends T> a, Stream<? extends T> b);合并2个流中的元素*/Stream<String> stream1 St…
阅读更多...
石子合并+环形石子合并+能量项链+凸多边形的划分——区间DP

石子合并+环形石子合并+能量项链+凸多边形的划分——区间DP

一、石子合并 (经典例题) 设有 N 堆石子排成一排&#xff0c;其编号为 1,2,3,…,N。 每堆石子有一定的质量&#xff0c;可以用一个整数来描述&#xff0c;现在要将这 N 堆石子合并成为一堆。 每次只能合并相邻的两堆&#xff0c;合并的代价为这两堆石子的质量之和&#xff0c;…
阅读更多...
python系统学习Day2

python系统学习Day2

section3 python Foudamentals part one&#xff1a;data types and variables 数据类型&#xff1a;整数、浮点数、字符串、布尔值、空值 #整型&#xff0c;没有大小限制 >>>9 / 3 #3.0 >>>10 // 3 #3 地板除 >>>10 % 3 #1 取余#浮点型&#xff…
阅读更多...
[职场] 优质简历怎么做 #学习方法#笔记

[职场] 优质简历怎么做 #学习方法#笔记

优质简历怎么做 简历是求职的“敲门砖”&#xff0c;直接影响着求职成败。然而&#xff0c;不少求职者对简历不太重视&#xff0c;认为简历就是写自己的经历。因此&#xff0c;在招聘现场&#xff0c;常会看到这样的简历&#xff1a;有的是从某招聘网站直接下载而来&#xff0c…
阅读更多...
LeetCode “AddressSanitizer:heat-use-after-free on address“问题解决方法

LeetCode “AddressSanitizer:heat-use-after-free on address“问题解决方法

heat-use-after-free &#xff1a; 访问堆上已经被释放的内存地址 现象&#xff1a;同样代码在LeetCode上报错&#xff0c;但是自己在IDE手动打印并不会报错 个人猜测&#xff0c;这个bug可能来源于LeetCode后台输出打印链表的代码逻辑问题。 问题描述 题目来自LeetCode的8…
阅读更多...
五官行为检测（表情基）解决方案提供商

五官行为检测（表情基）解决方案提供商

随着人工智能技术的日益成熟&#xff0c;情感识别与行为分析在企业界的应用逐渐广泛。美摄科技作为业内领先的五官行为检测&#xff08;表情基&#xff09;解决方案提供商&#xff0c;致力于为企业提供高效、精准的情感识别与行为分析服务。 美摄科技的五官行为检测&#xff0…
阅读更多...
Linux系统编程（四）进程

Linux系统编程（四）进程

一、进程的产生&#xff08;fork&#xff09; fork(2) 系统调用会复制调用进程来创建一个子进程&#xff0c;在父进程中 fork 返回子进程的 pid&#xff0c;在子进程中返回 0。 #include <sys/types.h> #include <unistd.h>pid_t fork(void); fork 后子进程不继…
阅读更多...
java 调用智谱ai 大模型的完整步骤（国内的 AI 大模型 对话）

java 调用智谱ai 大模型的完整步骤（国内的 AI 大模型 对话）

要使用java 调用智谱AI的API进行异步调用&#xff0c;您需要遵循以下步骤&#xff1a; 1. **获取API密钥**&#xff1a; - 您需要从智谱AI平台获取一个API密钥&#xff08;API Key&#xff09;&#xff0c;这个密钥将用于所有API请求的身份验证。 2. **SDK源…
阅读更多...
使用第三方幻兽帕鲁应用模板部署游戏后，是否需要更新？

使用第三方幻兽帕鲁应用模板部署游戏后，是否需要更新？

需要更新&#xff0c;因为幻兽帕鲁官方客户端更新&#xff0c;所以服务器也需要同步更新&#xff0c;才能继续游玩。版本不一致的话&#xff0c;是不能进入游戏的。 有两种更新方法&#xff1a; 如果你使用幻兽帕鲁应用模板部署游戏&#xff0c;那么可以选择使用游戏配置面板一…
阅读更多...
Android14之Android Rust模块编译语法(一百八十七)

Android14之Android Rust模块编译语法(一百八十七)

简介&#xff1a; CSDN博客专家&#xff0c;专注Android/Linux系统&#xff0c;分享多mic语音方案、音视频、编解码等技术&#xff0c;与大家一起成长&#xff01; 优质专栏&#xff1a;Audio工程师进阶系列【原创干货持续更新中……】&#x1f680; 优质专栏&#xff1a;多媒…
阅读更多...
【AI视野·今日CV 计算机视觉论文速览 第298期】Fri, 26 Jan 2024

【AI视野·今日CV 计算机视觉论文速览 第298期】Fri, 26 Jan 2024

AI视野今日CS.CV 计算机视觉论文速览 Fri, 26 Jan 2024 Totally 71 papers &#x1f449;上期速览✈更多精彩请移步主页 Daily Computer Vision Papers Multimodal Pathway: Improve Transformers with Irrelevant Data from Other Modalities Authors Yiyuan Zhang, Xiaohan …
阅读更多...
springboot登录校验

springboot登录校验

一、登录功能 二、登录校验 2.1 会话技术 2.2 JWT令牌 JWT令牌解析&#xff1a; 如何校验JWT令牌&#xff1f;Filter和Interceptor两种方式。 2.3 过滤器Filter 2.3.1 快速入门 修改上述代码&#xff1a; 2.3.2 详解 2.3.3 登录校验-Filter 2.4 Interceptor拦截器 2.4.1 …
阅读更多...
Ps：创建联系表

Ps：创建联系表

Ps菜单&#xff1a;文件/自动/联系表 II Automate/Contact sheet II Photoshop 的“联系表 II” Contact Sheet II命令为快速生成图像集合的预览和打印目录提供了一种高效的方法。 此命令可以通过自动化过程读取指定的图像文件&#xff0c;然后根据用户定义的参数&#xff08;如…
阅读更多...
【C++关联式容器】unordered_set

【C++关联式容器】unordered_set

目录 unordered_set 1. 关联式容器额外的类型别名 2. 哈希桶 3. 无序容器对关键字类型的要求 4. Member functions 4.1 constructor、destructor、operator 4.1.1 constructor 4.1.2 destructor 4.1.3 operator 4.2 Capacity ​4.2.1 empty 4.2.2 size 4.2.3 max…
阅读更多...
人工智能时代

人工智能时代

一、人工智能发展历史：从概念到现实 人工智能（Artificial Intelligence，简称AI）是计算机科学领域中一门旨在构建能够执行人类智能任务的系统的分支。其发展历程充满曲折，从概念的提出到如今的广泛应用，是技术、理论和实践相互交织的产物。 1. 起源（20世纪中期） 人工智…
阅读更多...
代码随想录算法训练营Day27|回溯算法·组合总和、组合总和II、分割回文串

代码随想录算法训练营Day27|回溯算法·组合总和、组合总和II、分割回文串

组合总和 class Solution{ private:vector<vector<int>>result;vector<int>path;void backtracking(vector<int>& candidates,int target,int sum,int startIndex){if(sum > target){return;}if(sum target){result.push_back(path);return;}…
阅读更多...
混合键合（Hybrid Bonding）工艺解读

混合键合（Hybrid Bonding）工艺解读

随着半导体技术的持续演进&#xff0c;传统的二维芯片缩放规则受到物理极限的挑战&#xff0c;尤其是摩尔定律在微小化方面的推进速度放缓。为了继续保持计算性能和存储密度的增长趋势&#xff0c;业界开始转向三维集成电路设计与封装技术的研发。混合键合技术就是在这样的背景…
阅读更多...
【前端实战小项目】学成在线网页制作

【前端实战小项目】学成在线网页制作

文章目录 1.项目准备1.1 项目目录 2.头部区域2.1 头部区域布局2.2 logo制作2.2 导航制作技巧(nav)2.3搜索区域(search)2.3用户区域(user区域) 3.banner区域3.1 总体布局3.2 左侧侧导航(left)3.3 右侧课程表(left) 4.精品推荐区域(recommend)5.精品课程( course)6.前端开发工程师…
阅读更多...
MySQL数据库基础（二）：MySQL数据库介绍

MySQL数据库基础（二）：MySQL数据库介绍

文章目录 MySQL数据库介绍 一、MySQL介绍 二、MySQL的特点 三、MySQL版本 四、MySQL数据库下载与安装 1、下载 2、安装 五、添加环境变量&#xff08;Windows&#xff09; 六、检测环境变量是否配置成功 MySQL数据库介绍 一、MySQL介绍 MySQL是一个关系型数据库管理…
阅读更多...
【Java多线程案例】定时器

【Java多线程案例】定时器

1. 定时器简介 定时器&#xff1a;想必大家一定对定时器这个概念不陌生&#xff01;因为它经常出现在我们的日常生活和编程学习中&#xff0c;定时器就好比是一个"闹钟"&#xff0c;会在指定时间处理某件事&#xff08;例如响铃&#xff09;&#xff0c;而在编程世界…
阅读更多...
最新文章

Copyright @ 2022~2023