二叉树 - 堆 | 数据结构中的小技巧大作用


在这里插入图片描述

📷 江池俊: 个人主页
🔥个人专栏: ✅数据结构冒险记 ✅C语言进阶之路
🌅 有航道的人,再渺小也不会迷途。


在这里插入图片描述

文章目录

    • 一、堆的概念及介绍
    • 二、结构图示
    • 三、堆的代码实现(图解)
      • 3.1 创建堆结构体即接口
      • 3.2 堆的初始化 && 交换两个数(用于parent 和 child 的交换 )
      • 3.3 堆的向上调整
      • 3.4 堆向下调整算法(以小堆为例)
      • 3.5 堆的创建
        • 【向上调整建堆时间复杂度】
        • 【向下调整建堆时间复杂度】
      • 3.6 堆的插入
      • 3.7 堆的删除
      • 3.8 取堆顶的数据
      • 3.9 求堆的数据个数
      • 3.10 堆的判空
    • 四、源代码
      • 4.1 Heap.h文件
      • 4.2 Heap.c文件
      • 4.3 Test.c文件

一、堆的概念及介绍

堆(Heap)是计算机科学中一类特殊的数据结构的统称。
堆通常是一个可以被看做一棵完全二叉树的数组。

需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事,一个是数据结构,一个是操作系统中管理内存的一块区域分段

堆满足下列性质:

  • 堆中某个节点的值总是不大于或不小于父节点的值。
  • 总是一棵完全二叉树

将根节点最大的堆叫做最大堆大根堆,根节点最小的堆叫做最小堆小根堆
在这里插入图片描述
在这里插入图片描述


二、结构图示

二叉堆是一颗完全二叉树,且堆中某个节点的值总是不大于其父节点的值,该完全二叉树的深度为 k,除第 k 层外,其它各层 (1~k-1) 的结点数都达到最大个数,第k 层所有的结点都连续集中在最左边。

其中堆的根节点最大称为最大堆,如下图所示:
在这里插入图片描述
我们可以使用数组存储二叉堆,右边的标号是数组的索引。
在这里插入图片描述

在这里插入图片描述

假设当前元素的索引位置为 i,可以得到规律:

parent(i) = i/2(取整)
left child(i) = 2*i+1
right child(i) = 2*i +2

三、堆的代码实现(图解)

3.1 创建堆结构体即接口

typedef int HPDataType; //数据元素类型
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap; //堆的结构

//堆的初始化 (可要可不要)
void HeapInit(Heap* hp);
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的销毁
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);

3.2 堆的初始化 && 交换两个数(用于parent 和 child 的交换 )

// 堆的初始化
void HeapInit(Heap* hp)
{
	assert(hp);

	hp->a = NULL;
	hp->size = 0;
	hp->capacity = 0;
}
//交换
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}

3.3 堆的向上调整

注意:此算法的前提是 在进行向上调整前此树已经是堆
向上调整操作用于在插入新元素时保持堆的性质。

算法思想如下:

  1. 首先,计算给定节点的父节点索引。如果当前节点是根节点(即索引为0),则没有父节点,不需要进行向上调整。

  2. 然后,进入一个循环,条件是当前节点的索引大于0。这是因为根节点已经是堆中的最大值(对于大顶堆)或最小值(对于小顶堆),无需再向上调整。

  3. 在循环中,比较当前节点和其父节点的值。如果当前节点的值小于其父节点的值(对于大顶堆)或大于其父节点的值(对于小顶堆),则需要进行向上调整。

  4. 交换当前节点和其父节点的值,将父节点移动到正确的位置。然后更新当前节点的索引为父节点的索引,并重新计算父节点的索引。

  5. 如果当前节点的值大于或等于其父节点的值(对于大顶堆)或小于或等于其父节点的值(对于小顶堆),则说明已经到达了正确的位置,可以跳出循环。

通过以上步骤,可以实现向上调整操作,确保堆的性质得到维护。
在这里插入图片描述

//向上调整 --- 插入时使用,保证堆的结构
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	//while(parent >= 0)
	while (child > 0)
	{
		if (a[child] < a[parent]) //< 改成 > 就是大堆的向上调整
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

时间复杂度分析
最坏的情况下是从第一个非叶子节点一路比较到根节点,比较的次数为完全二叉树的高度-1,即时间复杂度为 O(log2N)

3.4 堆向下调整算法(以小堆为例)

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

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

在这里插入图片描述

算法思想如下:

  1. 假设当前节点的左孩子为最小值节点。
  2. 判断当前节点是否有右孩子,如果有且右孩子的值小于左孩子的值,则将右孩子的下标赋值给child
  3. 如果当前节点的值大于child节点的值,说明需要向下调整,交换当前节点和child节点的值。
  4. 更新parentchild,继续向下调整。
  5. 如果当前节点的值小于等于child节点的值,说明已经找到合适的位置,跳出循环。

通过以上步骤,可以实现向下调整操作,确保堆的性质得到维护。
在这里插入图片描述

//向下调整
void AdjustDown(HPDataType* a, int size, int parent)
{
	//假设左孩子小
	int child = parent * 2 + 1;
	while (child < size)
	{
		//如果右孩子更小,则将child的下标置为右孩子的下标
		if (child + 1 < size && a[child] > a[child + 1]) //后面的 “>” 改成 “<”即为大堆的向下调整
		{
			child++;
		}

		if (a[child] < a[parent]) // “<”改成“>”即为大堆的向下调整
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

时间复杂度分析
最坏的情况即图示的情况,从根一路比较到叶子节点,比较的次数为完全二叉树的高度,即时间复杂度为 O(log2N)

3.5 堆的创建

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

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

在这里插入图片描述
【1】向上调整建堆

//向上调整建对堆 --- 0(N*logN)
int n = sizeof(a) / sizeof(a[0]);

for (int i = 1; i < n; i++)
{
	AdjustUp(a, i);
}

【2】向下调整建堆

// 向下要调整建堆 --- O(N) 
int n = sizeof(a) / sizeof(a[0]);
//找倒数第一个非叶子节点,从该节点位置开始往前一直到根节点,遇到一个节点,应用向下调整
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
	AdjustDown(a, n, i);
}

【3】模拟堆插入的过程建堆

// 堆的构建 --- 小堆 O(logN)
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	//模拟堆插入的过程建堆
	assert(hp);
	hp->a = (HPDataType*)malloc(sizeof(HPDataType)*n);
	hp->size = 0;
	hp->capacity = n;
	for (int i = 0; i < n; i++)
	{
		HeapPush(hp, a[i]);
	}
}
【向上调整建堆时间复杂度】

在这里插入图片描述

【向下调整建堆时间复杂度】

因为堆是完全二叉树,而满二叉树也是完全二叉树,此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值,多几个节点不影响最终结果):

在这里插入图片描述

3.6 堆的插入

先插入一个10到数组的尾上,再进行向上调整算法,直到满足堆。
在这里插入图片描述

// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if (hp->size == hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->size * 2;
		HPDataType* temp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (temp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		hp->a = temp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size++] = x;

	AdjustUp(hp->a, hp->size - 1);
}

3.7 堆的删除

删除堆是删除堆顶的数据,将堆顶的数据根最后一个数据一换,然后删除数组最后一个数据,再进行向下调整算法。

// 堆的删除
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);
}

3.8 取堆顶的数据

// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(hp->size > 0);

	return hp->a[0];
}

3.9 求堆的数据个数

// 求堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);

	return hp->size;
}

3.10 堆的判空

// 堆的判空
int HeapEmpty(Heap* hp)
{
	assert(hp);

	return hp->size == 0;
}

四、源代码

4.1 Heap.h文件

#pragma once

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

typedef int HPDataType; //数据元素类型
typedef struct Heap
{
	HPDataType* a;
	int size;
	int capacity;
}Heap; //堆的结构

//堆的初始化(可要可不要)
void HeapInit(Heap* hp);
// 堆的构建
void HeapCreate(Heap* hp, HPDataType* a, int n);
// 堆的销毁
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);

4.2 Heap.c文件

#define _CRT_SECURE_NO_WARNINGS 1

#include "Heap.h"


// 堆的初始化
void HeapInit(Heap* hp)
{
	assert(hp);

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

// 堆的构建 --- 小堆
void HeapCreate(Heap* hp, HPDataType* a, int n)
{
	assert(hp);
	hp->a = (HPDataType*)malloc(sizeof(HPDataType)*n);
	hp->size = 0;
	hp->capacity = n;
	for (int i = 0; i < n; i++)
	{
		HeapPush(hp, a[i]);
	}
}

// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);

	free(hp->a);
	hp->a = NULL;
	hp->size = hp->capacity = 0;
}

void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType temp = *p1;
	*p1 = *p2;
	*p2 = temp;
}


//向上调整 --- 插入时使用,保证堆的结构
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	//while(parent >= 0)
	while (child > 0)
	{
		if (a[child] < a[parent]) //< 改成 > 就是大堆的向上调整
		{
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

// 堆的插入 --- O(logN)
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	if (hp->size == hp->capacity)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->size * 2;
		HPDataType* temp = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (temp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		hp->a = temp;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size++] = x;

	AdjustUp(hp->a, hp->size - 1);
}

//向下调整 --- 删除的时候使用
void AdjustDown(HPDataType* a, int size, int parent)
{
	//假设左孩子小
	int child = parent * 2 + 1;
	while (child < size)
	{
		//如果右孩子更小,则将child的下标置为右孩子的下标
		if (child + 1 < size && a[child] > a[child + 1]) //后面的 “>” 改成 “<”
		{
			child++;
		}

		if (a[child] < a[parent]) // “<”改成“>”即为大堆的向下调整
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
	
}

// 堆的删除
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);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	assert(hp->size > 0);

	return hp->a[0];
}
// 求堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);

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

	return hp->size == 0;
}

4.3 Test.c文件

#define _CRT_SECURE_NO_WARNINGS 1

#include "Heap.h"

void Test1()
{
	int a[] = { 4,6,2,1,5,8,2,9 };
	Heap hp;
	int len = sizeof(a) / sizeof(a[0]);
	//HeapInit(&hp);
	模拟堆插入的过程建堆
	//for (int i = 0; i < len; i++)
	//{
	//	HeapPush(&hp, a[i]);
	//}
	HeapCreate(&hp, a, len);

	//打印堆中前k个元素
	/*int k = 4;
	while (k--)
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}*/
	//打印堆
	while (!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp)); 
		HeapPop(&hp);
	}
	printf("\n");
}

int main()
{
	Test1();
	return 0;
}

今天的分享到此结束,后续将继续向大家带来更多数据结构的小知识!

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

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

相关文章

6种解决msvcp140.dll文件丢失的有效方法讲解

msvcp140.dll是一个动态链接库文件&#xff0c;它是Microsoft Visual C 2015 Redistributable的一部分。这个文件通常位于Windows操作系统的System32文件夹中&#xff0c;它包含了许多用于支持C编程语言的函数和类。当您在运行一个需要使用这些函数和类的应用程序时&#xff0c…

cpp_12_异常处理

1 异常理论 1.1 何为异常&#xff1f; 在实际运行环境中发生&#xff0c;却在设计、编码、测试阶段无法预料的&#xff0c;各种潜在的问题。 1.2 报告异常的2种机制 1&#xff09;通过 return 返回值报告异常信息&#xff1a; 所有局部对象都能正确地被析构、被释放 定位错…

代码随想录算法训练营第四天 | 24.两两交换链表中的节点 19.删除链表的倒数第N个节点 160.链表相交 142.环形链表II

两两交换链表中的节点 两两交换节点&#xff0c;思路如下&#xff1a; 这样三步操作就实现了2和1两个节点的交换&#xff0c;循环操作&#xff0c;每一次循环移动到交换好的最后一个节点。循环的截止条件就是没有节点剩余了&#xff0c;或者只剩一个节点。翻转链表的精髓还是在…

机器学习实验报告- KNN算法

目录 一、算法介绍 1.1算法背景 1.2基本假设 1.3算法原理阐述 1.4算法关键点 二、数据集描述 2.1数据集介绍 2.2 数据处理 三、算法实现 3.1代码实现&#xff08;python&#xff09; 3.2代码复现结果 四、实验讨论 4.1关于KNN算法优缺点的讨论 4.2关于k值对实验结…

HTML JavaScript 数字变化特效

效果 案例一&#xff1a;上下滚动 案例二&#xff1a;本身变化 代码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8" /><meta http-equiv"X-UA-Compatible" content"IEedge" /><met…

【Python代码】以线性模型为例,详解深度学习算法流程,包括数据生成、定义模型、损失函数、优化算法和训练

**使用带有噪声的线性模型构造数据集&#xff0c;并根据有限的数据恢复该线性模型的参数。**其中包括数据集构造、模型参数初始化、损失函数定义、定义优化算法和训练等过程。是大多数算法实现过程的一个缩影&#xff0c;理解此过程有助于在开发或改进算法时更深刻了解其算法的…

【Oracle】收集Oracle数据库内存相关的信息

文章目录 【Oracle】收集Oracle数据库内存相关的信息收集Oracle数据库内存命令例各命令的解释输出结果例参考 【声明】文章仅供学习交流&#xff0c;观点代表个人&#xff0c;与任何公司无关。 编辑|SQL和数据库技术(ID:SQLplusDB) 【Oracle】收集Oracle数据库内存相关的信息 …

受电端协议芯片是如何让Type-C接口设备实现快充?

随着科技的不断进步&#xff0c;USB Type-C接口在电子产品中越来越普及。而在这个接口中&#xff0c;Type-c受电端协议芯片起着至关重要的作用。那么&#xff0c;什么是Type-c受电端协议芯片&#xff1f;它又是如何工作的呢&#xff1f;本文将为您揭开Type-c受电端协议芯片的神…

pip安装之后还是无法使用问题处理

最近由于需要使用到Python 相关功能&#xff0c; 记录下一些入门小技巧 1 python 下载安装 在window10 环境下载免安装版本&#xff0c; 并解压 安装包下载地址&#xff1a; https://www.python.org/ftp/python/3.12.1/python-3.12.1-embed-amd64.zip 2. 安装pip, 由于是内嵌…

QQ数据包解密

Windows版qq数据包格式&#xff1a; android版qq数据包格式&#xff1a; 密钥&#xff1a;16个0 算法&#xff1a;tea_crypt算法 pc版qq 0825数据包解密源码&#xff1a; #include "qq.h" #include "qqcrypt.h" #include <WinSock2.h> #include…

【php】php去除excel导入时的空格

背景 PHPExcel_1.8.0导入excel&#xff0c;遇到trim无法处理的空格。 解决方案 $excelVal preg_replace(“/(\s| | |\xc2\xa0)/”, ‘’, $excelVal); 完整代码 thinkphp5代码 function readExcel($file) {require_once EXTEND_PATH . PHPExcel_1.8.0/Classes/PHPExcel.p…

汽车制动器行业调查:市场将继续呈现稳中向好发展态势

汽车制动器是汽车的制动装置&#xff0c;汽车所用的制动器几乎都是摩擦式的&#xff0c;可分为鼓式和盘式两大类。鼓式制动器摩擦副中的旋转元件为制动鼓&#xff0c;其工作表面为圆柱面;盘式制动器的旋转元件则为旋转的制动盘&#xff0c;以端面为工作表面。 目前市场上主流的…

WebSocket-黑马好客租房

文章目录 网站中的消息功能如何实现&#xff1f;什么是WebSocket&#xff1f;http与websocket的区别httpwebsocket 浏览器支持情况快速入门创建itcast-websocket工程websocket的相关注解说明实现websocket服务测试编写js客户端 SpringBoot整合WebSocket导入依赖编写WebSocketHa…

全网最高质量文章:重新学习Java中的HashMap!!

前言 本文参考了美团技术团队的科普文章Java 8系列之重新认识HashMap - 知乎 (zhihu.com) 这篇文章的质量极其高&#xff0c;高到很有可能是全网介绍HashMap这个知识点最优秀的文章&#xff0c;没有之一&#xff01;&#xff01;&#xff01;因此&#xff0c;我决定在我自己的…

智能安全帽定制_基于联发科MT6762平台的智能安全帽方案

智能安全帽是一种具备多项功能的高科技产品&#xff0c;其功能集成了视频通话监控、高清图像采集、无线数据传输、语音广播对讲、定位轨迹回放、静默报警、危险救援报警、脱帽报警、碰撞报警、近电报警以及智能调度系统等&#xff0c;同时还支持多功能模块的自由添加&#xff0…

设计模式-责任链

之前写代码的时候看到过有审批场景使用了责任链&#xff0c;当时大概看了一下代码实现&#xff0c;今天终于有时间抽出来梳理一下&#xff0c;下面是本文的大纲&#xff1a; 使用场景 审批场景的普遍应用 实际案例&#xff1a;HttpClient中的责任链模式 责任链模式在事件处理、…

RocketMQ学习总结

一、架构 1、NameServer&#xff1a;注册中心。Broker信息注册到NameServer&#xff1b;producer/consumer根据某个topic通过NameServer获取对应broker的路由信息 &#xff1b; 2、Broker&#xff1a;负责存储、拉取、转发消息&#xff1b; 3、Producer&#xff1a;消息生产者…

creature_summon_groups

字段介绍 这个表保存了关于临时召唤生物的数据 creature_summon_groups summonerId&#xff08;召唤者ID&#xff09; summonerType 0 时&#xff0c;此处为 creature 的 entrysummonerType 1 时&#xff0c;此处为 gameobject 的 entrysummonerType 2 时&#xff0c;此处…

从设备维修到机器视觉:我的职业发展之路

大家好&#xff01;我是学员向工&#xff0c;今天很高兴有机会与大家分享我的职业经历。十年前&#xff0c;18岁中专毕业的那年&#xff0c;我踏入社会&#xff0c;至今已经过去了十年。一开始&#xff0c;我主要从事设备的维修、装配、钳工和电工等多岗位工作。 然而&#xff…

大数据关联规则挖掘:Apriori算法的深度探讨

文章目录 大数据关联规则挖掘&#xff1a;Apriori算法的深度探讨一、简介什么是关联规则挖掘&#xff1f;什么是频繁项集&#xff1f;什么是支持度与置信度&#xff1f;Apriori算法的重要性应用场景 二、理论基础项和项集支持度&#xff08;Support&#xff09;置信度&#xff…