数据结构——lesson7二叉树 堆的介绍与实现

前言💞💞

啦啦啦~这里是土土数据结构学习笔记🥳🥳

在这里插入图片描述
💥个人主页：大耳朵土土垚的博客
💥 所属专栏：数据结构学习笔记
💥对于数据结构顺序表链表有疑问的都可以在上面数据结构的专栏进行学习哦~ 欢迎大家🥳🥳点赞✨收藏💖评论哦~🌹🌹🌹 有问题可以写在评论区或者私信我哦~

一、 堆的概念及结构

如果有一个关键码的集合K = { k1，k2 ，k3 ，…，kn-1 }，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：ki <=k(2i+1 )且 ki<=k(2i+2) ( ki >=k(2i+1 )且 ki>=k(2i+2) ) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

堆的性质：

  1. 堆中某个节点的值总是不大于或不小于其父节点的值；
  2. 堆总是一棵完全二叉树。
    在这里插入图片描述

✨✨简单来说大堆指的是父节点都大于子节点的完全二叉树；
小堆指的是父节点都小于子节点的完全二叉树；
大堆的根节点是最大的，小堆是最小的。

二、堆的实现

1.堆的创建

我们给出一个数组，这个数组逻辑上可以看做一颗完全二叉树，但是还不是一个堆，现在我们通过算法，把它构建成一个堆。根节点左右子树不是堆，我们怎么调整呢？这里我们从倒数的第一个非叶子节点的子树开始调整，一直调整到根节点的树，就可以调整成堆。

下面是堆创建以及实现堆所需的函数，后文将一一介绍

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int HPDataType;
//构建一个结构体封装堆
typedef struct Heap
{
	HPDataType* a;//数组顺序表
	int size;//堆元素个数
	int capacity;//数组空间
}Heap;
//以下是实现堆的函数
// 堆的初始化
void HeapInit(Heap* hp);
// 堆的销毁
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);

2.堆的初始化

void HeapInit(Heap* hp)

//堆的初始化
void HeapInit(Heap* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->capacity = 0;
	hp->size = 0;
}

3.堆的删除（删除堆顶元素）

void HeapPop(Heap* hp)

在介绍堆的删除之前我们先介绍堆向下调整算法；
显而易见堆的删除不可能像顺序表那样删除尾部元素size–就行，我们需要玩点高深的，删除顶部元素，但删除顶部元素就没办法保证它删除后还是一个堆了，这就要利用我们下面介绍的向下调整算法。

int a[] = {1,8,3,5,7,6};

该数组逻辑结构可以看成一个完全二叉树如下图所示：
在这里插入图片描述

我们可以从图中看出它是一颗完全二叉树,但并不是所有的父节点都大于或小于其子节点，所以不是一个堆，接下来我们就可以通过下面介绍的堆向下调整算法将它调整为一个堆。

堆向下调整算法
现在我们给出一个数组，逻辑上看做一颗完全二叉树。我们通过从根节点开始的向下调整算法可以把它调整成一个小堆。
向下调整算法有一个前提：左右子树必须是一个堆，才能调整。

int array[] = {27,15,19,18,28,34,65,49,25,37};

在这里插入图片描述

🥳🥳 ①下面介绍第一种向下调整为小堆；
前提条件——左右子树都是小堆

//堆向下调整算法（小堆）
void AdjustDown(HPDataType* a, int n,int parent)
{
	
	int child = parent * 2 + 1;
	
	//向下调整
	while (parent < n)
	{
	//找到较小的孩子节点
		if (child + 1 < n && a[child] > a[child + 1])
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else
			break;
		
	}
}

因为要调整为小堆，所以要找到孩子中较小的一个进行比较；
如果父节点小于较小的孩子节点则直接break不需要调整，因为向下调整的前提条件是——左右子树都是小堆。
调整前：
在这里插入图片描述
调整后：在这里插入图片描述

💞💞Swap函数在这里

//交换函数
void Swap(HPDataType* a,HPDataType* b)
{
	HPDataType tmp = *a;
	*a = *b;
	*b = tmp;
}

🥳🥳②第二种向下调整为大堆；前提条件——左右子树都是大堆

//堆向下调整算法（大堆）
void AdjustDown(HPDataType* a, int n,int parent)
{
	
	int child = parent * 2 + 1;
	
	//向下调整
	while (child < n)
	{
	//找到较大的孩子节点
		if (child + 1 < n && a[child] < a[child + 1])
		{
			child++;
		}
		if (a[child] > a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else
			break;
		
	}
}

因为要调整为大堆，所以要找到孩子中较大的一个进行比较； 如果父节点大于于较大的孩子节点则直接break不需要调整，因为向下调整的前提条件是——左右子树都是大堆。

🎉🎉我们这里使用小堆向下调整，大家可以根据自己的需求选择哦~

学习完堆向下调整我们知道只要左右子树是一个堆，那么我们就可以从根节点开始向下调整直到整个二叉树成为一个堆；💫💫
所以删除堆顶元素我们就可以将堆顶元素与最后一个元素交换一下位置，这样除了根节点，其余父子关系都没变，左右子树还是堆，删除交换后的最后一个元素（也就是原来的根节点）；🎉🎉
我们再利用堆向下调整算法，将整个二叉树再次复原为堆。🥳🥳

堆顶元素删除

// 堆的删除，删除堆顶元素
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));//判空函数将在后文介绍
	
	//交换首尾元素
	Swap(&hp->a[0], &hp->a[hp->size - 1]);
	
	//size要记得--,表示删除元素
	hp->size--;
	
	//向下调整算法
	AdjustDown(hp->a, hp->size, 0);

}

4.堆的插入

void HeapPush(Heap* hp, HPDataType x)

我们知道堆的父节点必须都大于或小于子节点，那么往一个堆中插入元素是没办法保证大于或小于其父节点的，所以我们插入之后需要调整这个二叉树来保证堆；
这里就要用到堆向上调整算法了；注意下面是小堆的调整

堆向上调整算法

//向上调整
void AdjustUp(HPDataType* a,int child)
{
	//找到双亲节点
	int parent = (child - 1) / 2;
	//向上调整
	while (child > 0)
	{
		if (a[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
		
	}
}

堆向上调整类似于向下调整也有大堆小堆之分，大家可以依照堆的向下调整自己试试看写一下大堆的向上调整

堆的插入

// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	//判断容量
	if (hp->size == hp->capacity)//容量满了扩容
	{
		int newcapacity = hp->capacity == 0 ? 0 : 2 * hp->capacity;
		HPDataType* new = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (new == NULL)
		{
			perror("realloc fail");
			return;
		}
		hp->a = new;
		hp->capacity = newcapacity;
	}
	//尾插
	hp->a[hp->size] = x;
	hp->size++;
	//向上调整算法
	AdjustUp(hp->a,hp->size-1);
}

这里要注意插入数据要判断容量，如果满了要用realloc函数扩容，对于realloc函数有疑问的可以看土土的动态内存函数博客🎉🎉——c语言动态内存函数介绍；
如果第一次扩容，就将空间扩为4个HPDataType，其余扩原来的两倍

5. 取堆顶的数据

HPDataType HeapTop(Heap* hp);

// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(!HeapEmpty(hp));//判空
	return hp->a[0];//顶即下标为0的元素
}

6. 堆的数据个数

int HeapSize(Heap* hp)

// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->size;
}

堆的数据个数即为结构体中的size，直接返回即可

7.堆的销毁

void HeapDestory(Heap* hp)

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

，在内存中用realloc函数开辟空间用 free释放即可

💖💖判空函数在这里~
int HeapEmpty(Heap* hp)

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

8.堆实现代码如下

#include"Heap.h"
//堆的初始化
void HeapInit(Heap* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->capacity = 0;
	hp->size = 0;
}
// 堆的销毁
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 AdjustDown(HPDataType* a, int n,int parent)
{
	//找到较小的孩子节点
	int child = parent * 2 + 1;
	
	//向下调整
	while (child < n)
	{
		if (child + 1 < n && a[child] > a[child + 1])
		{
			child++;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else
			break;
		
	}
}

测试代码如下：

#include"Heap.h"
int main()
{
	Heap hp;
	HeapInit(&hp);
	int a[] = { 65,100,70,32,50,60 };
	for (int i = 0; i < 6; i++)
	{
		HeapPush(&hp, a[i]);
	}
	while (!HeapEmpty(&hp))
	{
		int top = HeapTop(&hp);
		printf("%d\n", top);
		HeapPop(&hp);
	}

	return 0;
	
}

运行结果如下：
在这里插入图片描述
居然是升序诶~大家知道原因吗
可以根据上面的代码和介绍理解为自己解答哦~

三、结语

以上就是堆的介绍和实现啦~✨✨需要注意的是堆有大堆小堆之分，相应的函数也就有两种，这里简单介绍了小堆的实现，大堆介绍了一点，大家可以通过上面介绍的自己探索大堆的实现，此外堆向上调整与向下调整是一个重难点大家要多花时间去理解与记忆哦 ~完结撒花 ~💖🎉🎉🥳

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

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

相关文章

计算机中丢失缺少mfc100.dll文件该如何解决?

计算机中丢失缺少mfc100.dll文件该如何解决?

当你打开某个应用程序时&#xff0c;有时候会遇到一个“mfc100.dll丢失”或找不到mfc100.dll的错误信息提示。这种情况表明你的计算机缺少一个名为mfc100.dll的动态链接库文件。这个文件是由Microsoft VC 2010 Redistributable Package提供的&#xff0c;它是一组可重用的组件&…
阅读更多...
普通专线维护成本太高？不如试试SD-WAN专线

普通专线维护成本太高？不如试试SD-WAN专线

企业数字化转型的加速&#xff0c;对于网络连接的需求变得越来越迫切。然而&#xff0c;传统的普通专线维护成本高、部署周期长等问题逐渐凸显&#xff0c;而SD-WAN&#xff08;软件定义广域网&#xff09;专线却因其灵活性和成本效益而备受关注。本文将探讨普通专线和SD-WAN专…
阅读更多...
idea2023和历史版本的下载

idea2023和历史版本的下载

1.idea中文官网 idea官网历史版本下载(https://www.jetbrains.com.cn/idea/download/other.html)
阅读更多...
配置与管理NFS服务器

配置与管理NFS服务器

配置与管理NFS服务器 NFS&#xff1a;即网络文件系统&#xff0c;只提供网络文件共享&#xff0c;不提供数据传输 作用&#xff1a;可以是用户在异构网络操作系统之间进行文件系统共享 概述&#xff1a;客户机与服务器之间可以共享文件&#xff0c;但不可数据传输功能&#…
阅读更多...
蓝桥杯-最长递增

蓝桥杯-最长递增

思路及代码详解:(此题为容易题) #include <iostream> using namespace std; int main() {int a[1000]{0};int n,temp;int num0;int count0;cin>>n;for(int i0;i<n;i){cin>>a[i];}//输入数据tempa[0];//设置一个临时比较的存储变量for(int i1;i<n;i){i…
阅读更多...
md5绕过

md5绕过

文章目录 \\和\\\md5数组绕过科学计数法绕过双md加密md5碰撞Hash长度攻击 下面会以同一道题给大家演示&#xff1a; (题目来源与nssctf) 和 在php代码中我们会看到和&#xff0c;虽然两个都是表示相等&#xff0c;但是在细节上会有所部区别 &#xff1a;是弱比较&#xff0c;只…
阅读更多...
C++错误总结（1）

C++错误总结（1）

1.定义函数类型时&#xff0c;如果没有返回值&#xff0c;用void void swap(int &x, int &y){ int tem x; x y; y tem; } 2.输入时&#xff0c;不加换行符 cin >> a >> b >> c >> endl ;(红色标记的是错误的部分) 3.【逆序出入…
阅读更多...
王道机试C++第 4 章 字符串：字符串内容详解及三个小程序 Day29

王道机试C++第 4 章 字符串：字符串内容详解及三个小程序 Day29

第 4 章 字符串 本章介绍一种基础数据类型——字符串&#xff0c;并且介绍一些字符串处理的方法及字符串匹配的方法。虽然字符串的内容非常基础&#xff0c;但是十分重要。希望读者能够好好学习本章的内容&#xff0c;为此后的学习打下良好的基础。 4.1 字符串内容详解 由于 …
阅读更多...
Vue事件处理:.passive修饰符与应用场景

Vue事件处理:.passive修饰符与应用场景

.passive修饰符 passive这个修饰符会执行默认方法。你们可能会问&#xff0c;明明默认执行为什么会设置这样一个修饰符。这就要说一下这个修饰符的本意了。 浏览器只有等内核线程执行到事件监听器对应的JavaScript代码时&#xff0c;才能知道内部是否会调用preventDefa…
阅读更多...
蓝桥杯练习题——归并排序

蓝桥杯练习题——归并排序

1.火柴排队 思路 1.求最小值的时候&#xff0c;可以直接按升序排序&#xff0c;这样得到的值就是最小值 2.求最小交换次数的时候&#xff0c;不能直接排序&#xff0c;因为只能交换相邻的数&#xff0c;只需要知道他们的相对大小&#xff0c;所以可以先用离散化&#xff0c;把…
阅读更多...
C及C++每日练习(3)

C及C++每日练习(3)

选择题&#xff1a; 1.以下程序的输出结果是&#xff08;&#xff09; #include <stdio.h> main() { char a[10] {1, 2, 3, 4, 5, 6, 7, 8, 9, 0}, *p; int i; i 8; p a i; printf("%s\n", p - 3); } A.6 B. 6789 C. 6 D.789 对于本题&#xff0…
阅读更多...
【视频图像取证篇】模糊图片复原车牌号技术原理和实战应用小结

【视频图像取证篇】模糊图片复原车牌号技术原理和实战应用小结

【视频图像取证篇】模糊图片复原车牌号技术原理和实战应用小结 模糊图片复原车牌号常用的技术原理和实战应用—【蘇小沐】 &#xff08;一&#xff09;运动模糊视频图像 由于各种各样的原因&#xff0c;主体或者拍摄设备运动共同造成的视频图像模糊等。 1、快门速度 快门速…
阅读更多...
【虚拟换衣+论文+代码】2403.OOTDiffusion：高分辨率(1024x768)可控的虚拟试穿（已开源，暂不能训练）

【虚拟换衣+论文+代码】2403.OOTDiffusion：高分辨率(1024x768)可控的虚拟试穿（已开源，暂不能训练）

项目地址&#xff1a;https://github.com/levihsu/OOTDiffusion 试用地址&#xff1a;https://ootd.ibot.cn/ 论文地址&#xff1a;2403.OOTDiffusion: 基于衣服融合的可控虚拟试穿潜在扩散 | readpaper arxiv: Outfitting Fusion based Latent Diffusion for Controllable Vir…
阅读更多...
第三节：在Sashulin中自定义组件

第三节：在Sashulin中自定义组件

上一节讲解了如何建立一个业务消息流&#xff0c;流程是由组件构成的。目前SMS提供了General、Database、MessageQueue、Socket、WebService、Http、Internet等系列常用组件&#xff0c;如果不满足业务需求&#xff0c;可以进行自定义组件开发。 一、组件开发 1、建立一个Jar…
阅读更多...
二维码门楼牌管理系统应用场景：推动旅游与文化产业的智慧化升级

二维码门楼牌管理系统应用场景：推动旅游与文化产业的智慧化升级

文章目录 前言一、二维码门楼牌管理系统在旅游领域的应用二、二维码门楼牌管理系统在文化产业的应用三、结语 前言 随着信息技术的不断发展&#xff0c;二维码门楼牌管理系统作为一种创新的信息化手段&#xff0c;正在逐渐渗透到旅游和文化领域。它通过为文化景点、旅游景点和…
阅读更多...
面试经典150题——两数相加

面试经典150题——两数相加

​Anything is worth "fighting for," and when you get it, dont doubt it, you deserve it, you deserve it. 1. 题目描述 2. 题目分析与解析 2.1 思路一 这个题目虽然标的是中等&#xff0c;但是大家看一下应该还是比较容易想到思路的&#xff0c;这不就相当于…
阅读更多...
华为通过FTP 进行文件操作示例

华为通过FTP 进行文件操作示例

通过FTP进行文件操作示例 组网图形 图1 通过FTP进行文件操作组网图 通过FTP进行文件操作简介配置注意事项组网需求配置思路操作步骤配置文件相关信息 通过FTP进行文件操作简介 配置设备作为FTP服务器&#xff0c;用户可以在终端通过FTP客户端软件访问设备&#xff0c;在本…
阅读更多...
深入理解 HTTP Authorization 头：基础知识

深入理解 HTTP Authorization 头：基础知识

在当今的互联网世界中&#xff0c;安全性贯穿于 web 应用的每个方面&#xff0c;HTTP Authorization 头的使用在这个过程中扮演着不可或缺的角色。它是 HTTP 请求中的一个重要部分&#xff0c;用来在客户端和服务器之间安全地传输认证信息。用途广泛&#xff0c;无论是浏览器还…
阅读更多...
外包干了1个多月，技术退步明显...

外包干了1个多月，技术退步明显...

&#x1f345; 视频学习&#xff1a;文末有免费的配套视频可观看 &#x1f345; 关注公众号【互联网杂货铺】&#xff0c;回复 1 &#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 这次来聊一个大家可能也比较关心的问题&#xff0c;那就是就业城…
阅读更多...
JS-04-javaScript数据类型和变量

JS-04-javaScript数据类型和变量

一、数据类型 计算机能处理的远不止数值&#xff0c;还可以处理文本、图形、音频、视频、网页等各种各样的数据&#xff0c;不同的数据&#xff0c;需要定义不同的数据类型。在JavaScript中定义了以下几种数据类型&#xff1a; 1-1、Number JavaScript不区分整数和浮点数&…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站