两篇文章讲透数据结构之堆（一）！

目录

1.堆的概念

2.堆的实现方式

3.堆的功能

4.堆的声明

5.堆的实现

5.1堆的初始化

5.2堆的插入

5.2.1向上调整算法

5.2.2堆的插入 

5.3堆的删除

5.3.1向下调整算法

5.3.2堆的删除

5.4获取堆顶元素

5.5获取堆的元素个数

5.6判断堆是否为空

5.7打印堆

5.8建堆

5.8.1向上调整建堆

5.8.2向下调整建堆

5.9销毁堆

1.堆的概念

堆（Heap）可以被看作一种特殊的数据结构，堆通常是一个可以被看成完全二叉树的数组对象。

根据堆的数值的关系，可以将堆分为两类:

  • 若满足任意结点的值>=其子结点的值，则可称为大根堆。
  • 若满足任意结点的值<=其子结点的值，则可称为小根堆。

通俗解释来说：

若是任意一个根结点的值都大于其子结点，则被称为大根堆，因为根大！

若是任意一个根结点的值都小于子结点，则是小根堆，因为根小！

2.堆的实现方式

既然堆是一种二叉树，那么我们就可以采用链式存储或者数组存储来实现这个数据结构。但是考虑到完全二叉树的特性，我们在这里采用数组存储的方式，因为这样既方便访问，也不会浪费空间。

既然使用数组存储，就会用到下标，而我们每次插入和删除，都需要计算父结点和子结点的位置。

现在我们取出大根堆的前五个元素，并总结一下父节点和子结点下标的关系。

我们可以总结出上图红字的规律，现在我们具体推导一下这个规律。

因此，我们可以得到如下结论：

  • 若双亲节点存在，则其下标为(i-1)/2。
  • 若孩子节点存在，左孩子下标为2i+1，右孩子为2i+2。

3.堆的功能

  • 堆的初始化。
  • 堆的插入。
  • 堆的删除。
  • 获取堆顶的元素。
  • 堆的元素个数。
  • 堆的判空。
  • 输出堆。
  • 建堆。
  • 销毁堆

4.堆的声明

因为我们是用数组创建堆的，因此堆的声明和顺序表的声明类似！ 

typedef int HpDataType;
typedef struct Heap
{
	HpDataType* a;//存储数据
	int size;//大小
	int capacity;//容量
}Heap

5.堆的实现

5.1堆的初始化

堆的初始化与顺序表的初始化类似。

void HeapInit(Heap* hp)//堆的初始化
{
	assert(hp);
	hp->a = NULL;//初始化的时候也可以不开空间
	hp->capacity = 0;
	hp->size = 0;
    //hp->size=hp->capacity=0;
}

5.2堆的插入

我们插入一个值进入堆，是进入到堆目前最后一个元素的后面吗？

其实并不一定，我现在给出大家这么一个场景。

如果目前有如此一个大堆：

现在我们要往里插入一个8，是插入到下标为5的地方吗？

肯定不是的，那么他应该插入到什么地方呢？ 

很显然，他应该取代掉5的位置，那么，新的堆就应该是下图：

 那么我们应该如何达到这个效果呢？

    我们刚刚已经计算了父节点和子节点的关系，而由于堆是一个完全二叉树，我们在这里先插入其左结点再插入右结点。而左节点和右节点之间是没有大小关系的，因此我们插入结点之后需要和其父节点比较大小关系，如果比父结点大的话就交换，小的话就不动即可。

    而如果第一次比较会发生交换，由于我们不确定它与更上一层的父结点的大小关系，因此我们还需要继续进行比较，直到不会发生交换为止。

    于是乎，向上调整算法诞生了！

5.2.1向上调整算法

void AdjustUp(Heap* hp, int child)//向上调整
{
	int parent = (child - 1) / 2;
	while (child > 0)//循环结束条件是孩子成为了根节点
	{
		if (hp->a[child] > hp->a[parent])
		{
			//交换
			swap(&hp->a[child], &hp->a[parent]);//这个函数自己写
			//更新新的父结点和子结点
			child = parent;
			parent = (child - 1) / 2;
		}
		//没有发生交换就跳出
		else
		{
			break;
		}
	}
}

5.2.2堆的插入 

现在我们就可以着手于完成堆的插入了。

void HeapPush(Heap* hp, HpDataType x)//堆的插入
{
	assert(hp);
	//判断是否开空间
	if (hp->size == hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity*2;
		HpDataType* tmp = (HpDataType*)realloc(hp->a, newcapacity * sizeof(HpDataType));
		if (!tmp)
		{
			perror("realloc fail");
			exit(1);
		}
		hp->a = tmp;
		hp->capacity = newcapacity;
	}
	//更新数值  后置++，先使用，再++
	hp->a[hp->size++] = x;
	AdjustUp(hp, hp->size - 1);
}

5.3堆的删除

堆的删除是删除堆顶元素，但是问题又出现了，删除了堆顶元素之后，后面的元素怎么办？顺着继承上去吗？那堆原来的亲属关系就全乱了，属实是父子叔侄变兄弟，闹了个哄堂大孝了。

那么这里我们要怎么处理呢？

我们在这里选择的处理方式是，先将堆顶元素和堆尾元素互换位置，之后直接让数组的长度-1。之后再调整根结点和其子节点之间的关系。调整的方法称为向下调整算法

5.3.1向下调整算法

刚刚已经介绍过了向上调整算法，我们也可以推测出向下调整算法的原理是和父节点和子节点的不断比较，但是这里又出现了一个问题，我们要和左子节点还是右子节点比较？

结论:

  • 大堆，则根结点和子结点中较大的值比较
  • 小堆，则根结点和子结点中较小的值比较

原理：这里以大堆为例，如果我们让根结点和较小的孩子值比较，而且发生了交换的话，那么现在的根结点是小于原来较大的孩子的，有悖于堆的定义。

现在我们实现一下向下调整算法

void AdjustDown(int* 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;
		}
	}
}

5.3.2堆的删除

堆的删除的思路刚刚已经说过了，我们现在完成它即可。 

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);
}

5.4获取堆顶元素

获取堆顶元素，首先要确保堆存在而且堆内有元素。

我们返回堆顶元素，直接返回数组中的第一个元素即可。

HpDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(hp->size > 0);
	return hp->a[0];
}

5.5获取堆的元素个数

获取堆的元素个数，就是返回堆的size，我们直接返回即可。

int HeapSize(Heap* hp)//堆的大小
{
	assert(hp);
	return hp->size;
}

5.6判断堆是否为空

判断堆是否为空，就是判断hp的size成员是否等于0，也是直接返回即可。

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

5.7打印堆

数组的打印谁不会啊？

void HeapDisplay(Heap* hp)//堆的打印
{
	for (int i = 0; i < hp->size; ++i)
	{
		printf("%d ", hp->a[i]);
	}
	printf("\n");
}

5.8建堆

建堆，就是给一个数组不断的调整，调整成为一个堆。

因此我们要传入的参数为堆、数组、数组长度。

首先，我们要在堆中开辟一块和数组空间等大的空间来存储数组元素。

之后，我们需要将参数中的数组中的元素拷贝到我们创建的空间中。

再之后，我们就可以通过我们的调整算法建堆了。

5.8.1向上调整建堆

向上调整建堆就是采用向上调整算法建堆，在这里我们可以用堆的插入取代上述开辟内存的操作。

void HeapCreatUp(Heap* hp, HpDataType* arr, int n)
{
	assert(hp && arr);
	//将每个元素向上调整即可
	for (int i = 0; i < n; i++)
	{
		HeapPush(hp, arr[i]);
	}
}

5.8.2向下调整建堆

向下调整建堆就是采取向下算法建堆，在这里我们首先要给堆开辟一个内存，然后拷贝内存，最后采用向下调整算法建堆即可。 

void HeapCreatDown(Heap* hp, HpDataType* arr, int n)
{
	assert(hp && arr);
	//给堆开辟内存
	HpDataType* tmp = (HpDataType*)malloc(sizeof(HpDataType) * n);
	if (tmp == NULL)
	{
		perror("malloc fail!");
		exit(-1);
	}
	hp->a = tmp;
	//将arr中的元素拷贝到堆中
	memcpy(hp->a, arr, sizeof(HpDataType) * n);
	hp->size = n;
	hp->capacity = n;
	//         最后一个父节点下标          父节点-1
	for (int i =((n - 1) - 1) / 2; i >= 0; i--)
	{                   
		AdjustDown(hp->a, n, i);
	}
}

5.9销毁堆

与顺序表的销毁方式一样，直接销毁即可。 

void HeapDestroy(Heap* hp)//销毁堆
{
	assert(hp);
	free(hp->a);
	hp->size = hp->capacity = 0;
}

6.堆的头文件

Heap.h

#include<stdio.h>
#include<string.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 AdjustUp(Heap* hp, int child);//向上调整
void HeapPush(Heap* hp, HpDataType x);//堆的插入
bool HeapEmpty(Heap* hp);//判断堆是否为空
size_t HeapSize(Heap* hp);//堆的大小
void AdjustDown(int* a, int n, int parent);//向下调整
void HeapPop(Heap* hp);//删除堆顶元素
HpDataType HeapTop(Heap* hp);//获取堆顶元素
void HeapDisplay(Heap* hp);//堆的打印
void HeapDestroy(Heap* hp);//销毁堆
void HeapCreatUp(Heap* hp, HpDataType* arr, int n);//向上调整建堆
void HeapCreatDown(Heap* hp, HpDataType* arr, int n);//向下调整建堆

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

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

相关文章

SQL开窗函数

SQL开窗函数

文章目录 概念&#xff1a;语法&#xff1a;常用的窗口函数及示例&#xff1a;求平均值&#xff1a;AVG() &#xff1a;求和&#xff1a;SUM():求排名&#xff1a;移动平均计数COUNT():求最大MXA()/小MIN()值求分区内的最大/最小值求当前行的前/后一个值 概念&#xff1a; 开窗…
阅读更多...
算法题1：电路开关（HW）

算法题1：电路开关（HW）

题目描述 实验室对一个设备进行通断测试，实验员可以操控开关进行通断，有两种情况： ps，图没记下来，凭印象画了类似的 初始时，3个开关的状态均为断开；现给定实验员操控记录的数组 records ，records[i] = [time, switchId]，表示在时刻 time 更改了开关 switchId 的状态…
阅读更多...
多线程（C++11）

多线程（C++11）

多线程&#xff08;C&#xff09; 文章目录 多线程&#xff08;C&#xff09;前言一、std::thread类1.线程的创建1.1构造函数1.2代码演示 2.公共成员函数2.1 get_id()2.2 join()2.3 detach()2.4 joinable()2.5 operator 3.静态函数4.类的成员函数作为子线程的任务函数 二、call…
阅读更多...
AOP编程

AOP编程

AOP编程 AOP&#xff0c;面向切面编程&#xff0c;一种编程范式&#xff0c;指导开发者如何组织程序结构。 OOP&#xff0c;面向对象编程&#xff0c;一种编程思想。 AOP&#xff0c;提供了一种机制,可以将一些横切系统中多个模块的共同逻辑(如日志记录、事务管理、安全控制等…
阅读更多...
SQL面试题练习 —— 波峰波谷

SQL面试题练习 —— 波峰波谷

来源&#xff1a;字节今日头条 目录 1 题目2 建表语句3 题解 1 题目 有如下数据&#xff0c;记录每天每只股票的收盘价格&#xff0c;请查出每只股票的波峰和波谷的日期和价格&#xff1b; 波峰定义&#xff1a;股票价格高于前一天和后一天价格时为波峰 波谷定义&#xff1a;股…
阅读更多...
MoE 系列论文解读：Gshard、FastMoE、Tutel、MegaBlocks 等

MoE 系列论文解读：Gshard、FastMoE、Tutel、MegaBlocks 等

节前&#xff0c;我们组织了一场算法岗技术&面试讨论会&#xff0c;邀请了一些互联网大厂朋友、今年参加社招和校招面试的同学。 针对大模型技术趋势、大模型落地项目经验分享、新手如何入门算法岗、该如何准备面试攻略、面试常考点等热门话题进行了深入的讨论。 总结链接…
阅读更多...
Unity在Windows平台播放HEVC/H.265格式视频的底层原理

Unity在Windows平台播放HEVC/H.265格式视频的底层原理

相关术语、概念 HEVC/H.265 HEVC&#xff08;High Efficiency Video Coding&#xff09;是一种视频压缩标准&#xff0c;也被称为H.265。它是一种高效的视频编码标准&#xff0c;可以提供比之前的标准&#xff08;如H.264&#xff09;更高的压缩率&#xff0c;同时保持较高的…
阅读更多...
力扣HOT100 - 31. 下一个排列

力扣HOT100 - 31. 下一个排列

解题思路&#xff1a; 数字是逐步增大的 步骤如下&#xff1a; class Solution {public void nextPermutation(int[] nums) {int i nums.length - 2;while (i > 0 && nums[i] > nums[i 1]) i--;if (i > 0) {int j nums.length - 1;while (j > 0 &&…
阅读更多...
015_表驱动编程思想(c实现)

015_表驱动编程思想(c实现)

【背景】 数据压倒一切。如果选择了正确的数据结构并把一切组织的井井有条&#xff0c;正确的算法就不言自明。编程的核心是数据结构&#xff0c;而不是算法。 ——Rob Pike 上面是这个名人说过的话&#xff0c;那么c语言之父 丹尼斯麦卡利斯泰尔里奇 的《c程序设计》里曾经…
阅读更多...
【Linux取经路】基于信号量和环形队列的生产消费者模型

【Linux取经路】基于信号量和环形队列的生产消费者模型

文章目录 一、POSIX 信号量二、POSIX 信号量的接口2.1 sem_init——初始化信号量2.2 sem_destroy——销毁信号量2.3 sem_wait——等待信号量2.4 sem_post——发布信号量 三、基于环形队列的生产消费者模型3.1 单生产单消费模型3.2 多生产多消费模型3.3 基于任务的多生产多消费模…
阅读更多...
C# 利用Xejen框架源码，我们来开发一个基于Dapper技术的数据库通用的帮助访问类，通过Dapper的增删改查，可以访问Sqlite数据库

C# 利用Xejen框架源码，我们来开发一个基于Dapper技术的数据库通用的帮助访问类，通过Dapper的增删改查，可以访问Sqlite数据库

Dapper 是一个轻量级的对象关系映射&#xff08;ORM&#xff09;工具&#xff0c;适用于 .NET 平台。它由 Stack Overflow 团队开发&#xff0c;旨在提供简单、高效的数据访问功能。与其他重量级 ORM&#xff08;如 Entity Framework&#xff09;相比&#xff0c;Dapper 更加轻…
阅读更多...
用这8种方法在海外媒体推广发稿平台上获得突破-华媒舍

用这8种方法在海外媒体推广发稿平台上获得突破-华媒舍

在今天的数字时代&#xff0c;海外媒体推广发稿平台已经成为了许多机构和个人宣传和推广的有效途径。如何在这些平台上获得突破并吸引更多的关注是一个关键问题。本文将介绍8种方法&#xff0c;帮助您在海外媒体推广发稿平台上实现突破。 1. 确定目标受众 在开始使用海外媒体推…
阅读更多...
C++语法｜虚函数与多态详细讲解（六）｜如何解释多态？（面试向）

C++语法｜虚函数与多态详细讲解（六）｜如何解释多态？（面试向）

系列汇总讲解&#xff0c;请移步&#xff1a; C语法&#xff5c;虚函数与多态详细讲解系列&#xff08;包含多重继承内容&#xff09; 多态分为了两种&#xff0c;一种是静态的多态&#xff0c;一种是动态的多态。 静态&#xff08;编译时期&#xff09;的多态 函数重载 boo…
阅读更多...
pands使用openpyxl引擎实现EXCEL条件格式

pands使用openpyxl引擎实现EXCEL条件格式

通过python的openpyxl库&#xff0c;实现公式条件格式。 实现内容&#xff1a;D列单元格不等于E列同行单元格时标红。 #重点是formula后面的公式不需要“”号。 from openpyxl.styles import Color, PatternFill, Font, Border from openpyxl.styles.differential import Dif…
阅读更多...
【设计模式】JAVA Design Patterns——Bytecode（字节码模式）

【设计模式】JAVA Design Patterns——Bytecode（字节码模式）

&#x1f50d;目的 允许编码行为作为虚拟机的指令 &#x1f50d;解释 真实世界例子 一个团队正在开发一款新的巫师对战游戏。巫师的行为需要经过精心的调整和上百次的游玩测试。每次当游戏设计师想改变巫师行为时都让程序员去修改代码这是不妥的&#xff0c;所以巫师行为以数据…
阅读更多...
git push后一直卡在在Writing objects:问题

git push后一直卡在在Writing objects:问题

git push后一直卡在Writing objects: 解决&#xff1a;设置 git config --global http.postBuffer 5242880000在执行git push。 一般设置后就可以成功了&#xff0c;后面不用看。 2. 我这里结果又报错&#xff1a; fatal: protocol error: bad line length 8192 MiB | 107.46 …
阅读更多...
【C++】d1

【C++】d1

关键字&#xff1a; 运行、前缀、输入输出、换行 运行f10 前缀必须项&#xff1a; #include <iostream> using namespace std; 输入/输出&#xff1a; cin >> 输入 cout << 输出 语句通过>>或<<分开 换行 endl或者"\n"
阅读更多...
想当安卓开发工程师？学习路线分享！

想当安卓开发工程师？学习路线分享！

安卓开发学习路线 在前几篇文章中，对安卓开发岗位的岗位要求做了一些科普，本节文章将介绍安卓开发岗位的学习路线。 目前，网络上有很多面经、算法题解、算法课等学习资料，如何合理利用这些资料成为技术求职者的一大困惑。笔者整理了一份安卓开发岗位学习路线供大家参考，…
阅读更多...
第四课 communcation服务-can配置第二弹

第四课 communcation服务-can配置第二弹

Davinci配置目标： 介绍DBC基本属性，并且配置出一个DBC。 将DBC导入到vector的davinci工具，生成我们想要的代码。 Davinci配置步骤： 1. 编辑DBC文件 DBC文件是一种非常重要的工具，所谓DBC就是Database CAN，CAN网络的数据库文件，定义了CAN网络的节点、消息、信号的所有…
阅读更多...
网络安全知识核心20要点

网络安全知识核心20要点

1、什么是SQL注入攻击 概述 攻击者在 HTTP 请求中注入恶意的 SQL 代码&#xff0c;服务器使用参数构建数据库 SQL 命令时&#xff0c;恶意SQL 被一起构造&#xff0c;并在数据库中执行。 注入方法 用户登录&#xff0c;输入用户名 lianggzone&#xff0c;密码‘ or ‘1’’…
阅读更多...
最新文章

Copyright @ 2022~2023