二叉树(2)——堆的实现

  •   堆表面是数组,内核是完全二叉树/满二叉树
  •   在插入删除的时候要注意操作过后堆是否还是一个堆,要进行交换等操作。(向上调整
  •   逻辑上控制二叉树,物理上控制数组!!!

接下来我们用【小堆】来介绍堆的代码实现。

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

Heap.c

HeapInit初始化

void HeapInit(HP* php)
{
	assert(php);

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

HeapDestroy销毁

void HeapDestroy(HP* php)
{
	assert(php);

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

HeapPush插入数据

  • 这里要注意在一个堆后插入一个数,这个堆是否还是堆的问题。所以要将插入的数和他的父亲进行比较。
  • 同时要考虑,如何使一个随机的数组排列成堆?这个问题在test.c中就可解决。

Swap函数实现

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

AdjustUp函数实现

  • 理解判断条件:child > 0
  • 首先比较插入的数和它的父亲,然后进行判断。
  • 若满足判断条件,就交换两个数的位置,并让child向上调整到parent的位置,让parent向上调整到它的父亲的位置,依此类推。
void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;
	//while (parent >= 0) 不能这样写,因为parent不可能<0
	while (child > 0) //用child判断
	{
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			//往上走
			child = parent;
			parent = (child - 1) / 2;
			//child = (child - 1) / 2;
			//parent = (parent - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

HeapPush函数实现

  • 时间复杂度为O(logN),也就是高度次。
void HeapPush(HP* php, HPDataType x)
{
	assert(php);
	if (php->size == php->capacity)
	{
		int newCapacity = php->capacity == 0 ? 4 : php->capacity * 2;
		HPDataType* tmp = (HPDataType*)realloc(php->a, newCapacity * sizeof(HPDataType));
		if (tmp == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
			php->a = tmp;
			php->capacity = newCapacity;
	}
	php->a[php->size] = x;
	php->size++;

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

HeapPop删除数据 

  • 删除根
  • 不能用挪动覆盖法,堆会彻底乱掉,且时间复杂度是O(N)。
  • 方法:首尾交换再尾删,然后向下调整。 这样左右子树依旧是小堆。时间复杂度为O(logN)。
  • 如何判断叶子? 叶子*2+1>size

Swap函数实现

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

AdjustDown函数实现

  • 越界问题:这里要注意在while里一定要加上【child+1<size】这个判断条件,因为如果child是完全二叉树叶子的左孩子,而且没有右孩子的情况,那么【if (a[child + 1] < a[child])】这个child+1就会越界。
void AdjustDown(int* a, int size, int parent)
{
	//假设左孩子小,如果事实是右孩子小,那么就更新child
	int child = parent * 2 + 1;
	while (child+1 < size && child < size)
	{
		if (a[child + 1] < a[child])
		{
			++child;
		}
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
	
}

HeapPop函数实现

void HeapPop(HP* php)
{
	assert(php);
	assert(php->size > 0);
	//首尾交换
	Swap(&php->a[0], &php->a[php->size - 1]);
	//删除
	php->size--;
	//向下调整
	AdjustDown(php->a, php->size, 0);
}

 HeapTop取堆顶元素

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

	return php->a[0];
}

HeapSize堆元素个数

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

 HeapEmpty判断是否为空

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

Test.c

首先测试一下插入。

  • ⭐要注意这里使用了for循环,将数组中的数一个一个插入,然后排列成堆。这样就能保证这个数组是一个堆啦!
int main()
{
	int a[] = { 4,6,2,1,5,8,2,9};
	HP hp;
	HeapInit(&hp);
	for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
	{
		HeapPush(&hp, a[i]);
	}

	while (!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
	printf("\n");

	return 0;
}

测试取数组中前k个小的元素。

  • 这里先将数组里的数据排列成一个小堆,然后用while循环, 取一个堆顶元素删一个。
int main()
{
	int a[] = { 4,6,2,1,5,8,2,9};
	HP hp;
	HeapInit(&hp);
	for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
	{
		HeapPush(&hp, a[i]);
	}

	int k = 3;
	while (k--)
	{
		printf("%d\n", HeapTop(&hp));
		HeapPop(&hp);
	}

	return 0;
}

输出小堆

int main()
{
	int a[] = { 4,6,2,1,5,8,2,9};
	HP hp;
	HeapInit(&hp);
	for (int i = 0; i < sizeof(a) / sizeof(int); ++i)
	{
		HeapPush(&hp, a[i]);
	}

	while (!HeapEmpty(&hp))
	{
		printf("%d ", HeapTop(&hp));
		HeapPop(&hp);
	}
	printf("\n");

	return 0;
}

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

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

相关文章

小白水平理解面试经典题目LeetCode 21. Merge Two Sorted Lists【Linked List类】

21. 将两个有序列表融合 Linked List 数据结构也在面试中经常出现&#xff0c;作为很好处理客户信息存储的结构很方便&#xff0c;也是重点必会项目之一&#xff0c;看看我们如何教懂白月光&#xff0c;成功邀约看电影吧。 小白渣翻译 你将获得两个排序链表 list1 和 list2 …

Hudi学习 6:Hudi使用

准备工作&#xff1a; 1.安装hdfs https://mp.csdn.net/mp_blog/creation/editor/109689143 2.安装spark spark学习4&#xff1a;spark安装_hzp666的博客-CSDN博客 3.安装Scala Hudi学习6&#xff1a;安装和基本操作_hzp666的博客-CSDN博客 spark-shell 写入和读取hudi 2.…

【Rust】——rust前言与安装rust

&#x1f383;个人专栏&#xff1a; &#x1f42c; 算法设计与分析&#xff1a;算法设计与分析_IT闫的博客-CSDN博客 &#x1f433;Java基础&#xff1a;Java基础_IT闫的博客-CSDN博客 &#x1f40b;c语言&#xff1a;c语言_IT闫的博客-CSDN博客 &#x1f41f;MySQL&#xff1a…

力扣热门100题刷题笔记 - 10. 正则表达式匹配

力扣热门100题 - 10. 正则表达式匹配 题目链接&#xff1a;10. 正则表达式匹配 题目描述&#xff1a; 给你一个字符串 s 和一个字符规律 p&#xff0c;请你来实现一个支持 . 和 * 的正则表达式匹配。 . 匹配任意单个字符 * 匹配零个或多个前面的那一个元素 所谓匹配&#xff…

数据库管理-第144期 深入使用EMCC-01(20240204)

数据库管理144期 2024-02-04 数据库管理-第144期 深入使用EMCC-01&#xff08;20240204&#xff09;1 用户管理2 配置告警动作3 配置意外事件规则总结 数据库管理-第144期 深入使用EMCC-01&#xff08;20240204&#xff09; 作者&#xff1a;胖头鱼的鱼缸&#xff08;尹海文&am…

Abap与eCharts

一&#xff0c;简介 利用html与eCharts来绘图&#xff0c;然后用cl_gui_html_viewer将html呈现到abap屏幕中。 二&#xff0c;使用eCharts画图 在一个文件夹中准备如下文件&#xff0c;index.html和echarts.js是必须的&#xff0c;data.json(作为数据源)和jquery.js如果用到就可…

问题:下列关于海关统计项目的表述,正确的有:A.进出境货物的统计重量和数量应以报关单位申报的重量和数 #笔记#职场发展#媒体

问题&#xff1a;下列关于海关统计项目的表述&#xff0c;正确的有&#xff1a;A&#xff0e;进出境货物的统计重量和数量应以报关单位申报的重量和数 下列关于海关统计项目的表述&#xff0c;正确的有&#xff1a; A&#xff0e;进出境货物的统计重量和数量应以报关单位申报的…

SERVLET间通信

在Web应用程序中,应用程序的servlet等各种组件之间可能需要通信以便处理客户机请求。例如,假设Web应用程序中有一个servlet显示组织的版权信息。您可以使用各种servelt通信技术将此servlet的内容纳入到需要显示版权信息的所有其他应用程序servlet中。同样,如果处理请求时发生…

2024年第三届能源与环境工程国际会议(CFEEE 2024) | Ei&Scopus双检索

会议简介 Brief Introduction 2024年第三届能源与环境工程国际会议(CFEEE 2024) 会议时间&#xff1a;2024年12月12日-14日 召开地点&#xff1a;澳大利亚凯恩斯 大会官网&#xff1a;CFEEE 2024-2024 International Conference on Frontiers of Energy and Environment Engine…

板块零 IDEA编译器基础:第一节 安装IDEA 来自【汤米尼克的JAVAEE全套教程专栏】

板块零 IDEA编译器基础&#xff1a;第一节 安装IDEA 一、为什么选择IDEA IU&#xff1f;&#xff08;1&#xff09;对比Eclipse&#xff08;2&#xff09;对比VScode&#xff08;3&#xff09;对比IDEA 社区版 二、IDEA IU 下载全过程 此套教程将全系列使用IDEA IU&#xff08…

Leetcode刷题笔记题解(C++):1863. 找出所有子集的异或总和再求和

思路如下&#xff1a;递归思路&#xff0c;依次遍历数组中的数&#xff0c;当前数要不要选择像二叉树一样去遍历如下图所示 0 0 &#xff08;选5&#xff09; 5&#xff08;不选5&#xff09; 0 1 0 1 0 6 …

java之spring事务管理

spring事务管理 1. 事务概念 事务是一组操作的集合&#xff0c;是一个不可 分割的工作单位&#xff0c; 这些操作&#xff0c;要么同时成功&#xff0c;要么同时失败 和mysql数据库的事务管理道理一样。开启事务 start 提交事务 commit 回滚事务 rollback2.操作实现 Transa…

[小白]Linux安装jdk1.8[超详细]

1、前言 个人博客&#xff1a;www.wdcdbd.com 网站挂掉了可以邮件联系哦&#xff01;W17838335896163.com hello,刚学linux攻城狮们&#xff0c;应该也为安装jdk而烦恼吧&#xff0c;不过没关系&#xff0c;今天就像超详细的linux安装jdk1.8的详细过程发出来&#xff0c;争…

SpringCloud + Nacos环境下抽取Feign独立模块并支持MultipartFile

文章目录 一、前提条件和背景1. 前提2. 背景 二、Feign模块1. 依赖引入2. application.yaml配置3. 扩展支持MultipartFile4. 将media-api注册到feign 三、Media模块四、Content模块1. 引入依赖2. 启用FeignClient3. 测试 五、需要澄清的几点 一、前提条件和背景 1. 前提 已经…

计组学习笔记2024/2/5

记录每天学到了什么,同时在挪移图片过程中再次理解加深印象 学计算机最重要的是理解,而不是整齐的笔记,不要主次搞混,所以以后记笔记的模式也要改一下(主要还是自己太菜,还达不到一边做到整齐笔记的同时还能够有时间做到理解,所以只能舍弃整齐时间保留理解时间)(不过如果有现成…

JDK和Spring的SPI机制原理分析

目录 一、JDK 二、Spring框架介绍 三、SPI机制原理 一、JDK JDK是Java Development Kit的缩写&#xff0c;是Java开发工具包的意思。它是用于开发Java应用程序和运行Java程序的软件包。JDK包含了Java编译器&#xff08;javac&#xff09;和Java虚拟机&#xff08;JVM&#…

SpringBoot实战第二天

今日战报 继续完善用户相关接口开发&#xff1a; 1.完成获取用户信息功能 2.完成更新用户信息功能 3.完成更新用户头像功能 4.完成更新用户密码功能 获取用户信息 接口文档 如接口文档所示&#xff0c;我们需要做的就是从header中的Authorization中读取token&#xff0c;解码…

浅谈QT的几种线程的使用和区别。

简介&#xff1a; 线程是操作系统中的基本执行单元&#xff0c;是一个独立的执行路径。每个线程都有自己的栈空间&#xff0c;用于存储本地变量和函数调用的上下文。多个线程可以在同一进程中并发执行&#xff0c;从而实现并发处理&#xff0c;提高程序的性能和响应能力。 与进…

Unet 实战分割项目、多尺度训练、多类别分割

1. 介绍 之前写了篇二值图像分割的项目&#xff0c;支持多尺度训练&#xff0c;网络采用backbone为vgg的unet网络。缺点就是没法实现多类别的分割&#xff0c;具体可以参考&#xff1a;二值图像分割统一项目 本章只对增加的代码进行介绍&#xff0c;其余的参考上述链接博文 本…

追觅发布多款旗舰新品,双机械臂扫地机器人X40领衔登场

2月2日&#xff0c;追觅科技全球首创仿生“双”机械臂新品发布会在苏州举行。会上&#xff0c;追觅科技中国区总裁郭人杰分享了追觅科技全球化发展的业绩成果。郭人杰称&#xff0c;2019-2023年&#xff0c;追觅科技5年复合年增长率超过100%&#xff0c;增速领跑智能清洁行业&a…