二叉树顺序结构堆实现

目录

Test.c测试代码

test1

test2

test3

🎇Test.c总代码 

Heap.h头文件&函数声明

头文件

函数声明

🎇Heap.h总代码

Heap.c函数实现 

☁HeapInit初始化

☁HeapDestroy销毁

☁HeapPush插入数据

【1】插入数据

【2】向上调整Adjustup❗

数据交换Swap

☁HeapPop删除数据

【1】交换数据

【2】删除数据

【3】向下调整Adjustdown❗

假设法找Child 

数据交换Swap

☁HeapTop堆顶元素

☁HeapSize堆元素个数

☁HeapEmpty判断为空否

🎇Heap.c总代码 

拖了很久的【堆】，本周主要学习就是【数据结构】。本章【堆】是以【小堆】为例子。

  •  堆表面是数组，内核是完全二叉树/满二叉树
  • ❗HeapPush
  • ❗HeapPop
  • 函数如果需要多次复用才会提取出来
  • free会对NULL进行检查 
  • 用循环写起来很方便的代码就不要使用递归
  • do while循环用于无论循环条件如何，循环都会执行一次
  • 步骤--注意事项--循环结束条件--时间复杂度（下篇重点讲）

Test.c测试代码

#include"Heap.h"
int main()
{
	HP php;
	//HP*ph=&php
	//test1(&php);
	test2(&php);
	test3(&php);
	return 0;
}

test1

//建堆
void test1(HP* ph)
{
	int a[] = { 4,5,3,7,8,2,1,9,10 };
	HeapInit(ph);
	int i = 0;
	for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		HeapPush(ph, a[i]);
	}
}

test2

//找出堆的前K个数字
void test2(HP* ph)
{
	int a[] = { 4,5,3,7,8,2,1,9,10 };
	HeapInit(ph);
	int i = 0;
	int k = 5;
	for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		HeapPush(ph, a[i]);
	}

	while (k--)
	{
		printf("%d ", HeapTop(ph));
		HeapPop(ph);
	}
	printf("\n");
}

 

test3

//排序--升序
void test3(HP* ph)
{
	int a[] = { 4,5,3,7,8,2,1,9,10 };
	HeapInit(ph);
	int i = 0;
	for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		HeapPush(ph, a[i]);
	}
	while (HeapEmpty(ph))//为NULLflase
	{
		printf("%d ", HeapTop(ph));
		HeapPop(ph);
	}
}

🎇Test.c总代码 

#include"Heap.h"
//建堆
void test1(HP* ph)
{
	int a[] = { 4,5,3,7,8,2,1,9,10 };
	HeapInit(ph);
	int i = 0;
	for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		HeapPush(ph, a[i]);
	}
}

//找出堆的前K个数字
void test2(HP* ph)
{
	int a[] = { 4,5,3,7,8,2,1,9,10 };
	HeapInit(ph);
	int i = 0;
	int k = 5;
	for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		HeapPush(ph, a[i]);
	}

	while (k--)
	{
		printf("%d ", HeapTop(ph));
		HeapPop(ph);
	}
	printf("\n");
}

void test3(HP* ph)
{
	int a[] = { 4,5,3,7,8,2,1,9,10 };
	HeapInit(ph);
	int i = 0;
	for (i = 0; i < sizeof(a) / sizeof(a[0]); i++)
	{
		HeapPush(ph, a[i]);
	}
	while (HeapEmpty(ph))//为NULLflase
	{
		printf("%d ", HeapTop(ph));
		HeapPop(ph);
	}
}

int main()
{
	HP php;
	//HP*ph=&php
	//test1(&php);
	test2(&php);
	test3(&php);
	return 0;
}

Heap.h头文件&函数声明

头文件

#pragma once
#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<stdlib.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.h总代码

#pragma once
#include<stdio.h>
#include<string.h>
#include<assert.h>
#include<stdlib.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初始化

#include"Heap.h"
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);//不用担心为NULL，free会对NULL做检查
	php->size = php->capacity = 0;
}

☁HeapPush插入数据

 先插入一个10到数组的尾上，再进行向上调整算法，直到满足堆。

【1】插入数据

void HeapPush(HP* php, HpDataType x)
{
	assert(php);
	//扩容
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HpDataType* tmp = (HpDataType*)realloc(php->a, newcapacity * sizeof(HpDataType));
		if (tmp == NULL)
		{
			printf("fail realloc");
			return;
		}
		php->capacity = newcapacity;
		php->a = tmp;
	}
	//插入数据
	php->a[php->size] = x;
	php->size++;
	//向上调整//数组，调整元素下标
	AdjustUp(php->a, php->size - 1);
}

【2】向上调整Adjustup❗

//向上调整算法
void AdjustUp(HpDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while ( child > 0 )//此刻parent已经数组越界
	{
		if (a[child] < a[parent])
		{
			//交换
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else//child>=parent
		{
			break;
		}
	}
}
数据交换Swap
//交换
void Swap(HpDataType* H1, HpDataType* H2)
{
	HpDataType tmp = *H1;
	*H1 = *H2;
	*H2 = tmp;
}

☁HeapPop删除数据

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

//删除
void HeapPop(HP* php)
{
	assert(php);
	assert(php->size);

	//1.交换
	Swap(&php->a[0], &php->a[php->size - 1]);

	//2.删除
	php->size--;

	//3.向下调整--数组，结束条件size有关，调整的位置parent
	Adjustdown(php->a, php->size, 0);
}

【1】交换数据

	//1.交换
	Swap(&php->a[0], &php->a[php->size - 1]);

【2】删除数据

	//2.删除
	php->size--;

【3】向下调整Adjustdown❗

//3.向下调整--数组，结束条件size有关，调整的位置parent
Adjustdown(php->a, php->size, 0);
//向下调整
void Adjustdown(HpDataType* a, int size, int parent)
{
	//假设法
	int child = parent * 2 + 1;
	while (child < size )//why child < size && child+1<size
	{
		if (child + 1 < size && a[child + 1] < a[child])
		{
			child++;
		}
		//比较
		if (a[child] < a[parent])
		{
			//交换
			Swap(&a[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else//>=
		{
			break;
		}
	}
}
假设法找Child 
	int child = parent * 2 + 1;
    if (a[child + 1] < a[child])
	{
		child++;
	}
数据交换Swap
//交换
void Swap(HpDataType* H1, HpDataType* H2)
{
	HpDataType tmp = *H1;
	*H1 = *H2;
	*H2 = tmp;
}

☁HeapTop堆顶元素

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

	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;//!=0是true不为NULL执行   ==0 flase 不执行
}

🎇Heap.c总代码 

#include"Heap.h"
void HeapInit(HP* php)
{
	assert(php);
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

void HeapDestroy(HP* php)
{
	assert(php);
	free(php->a);//不用担心为NULL，free会对NULL做检查
	php->size = php->capacity = 0;
}
//交换
void Swap(HpDataType* H1, HpDataType* H2)
{
	HpDataType tmp = *H1;
	*H1 = *H2;
	*H2 = tmp;
}

//向上调整算法
void AdjustUp(HpDataType* a, int child)
{
	int parent = (child - 1) / 2;
	while ( child > 0 )//此刻parent已经数组越界
	{
		if (a[child] < a[parent])
		{
			//交换
			Swap(&a[child], &a[parent]);
			child = parent;
			parent = (parent - 1) / 2;
		}
		else//child>=parent
		{
			break;
		}
	}
}

void HeapPush(HP* php, HpDataType x)
{
	assert(php);
	//扩容
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		HpDataType* tmp = (HpDataType*)realloc(php->a, newcapacity * sizeof(HpDataType));
		if (tmp == NULL)
		{
			printf("fail realloc");
			return;
		}
		php->capacity = newcapacity;
		php->a = tmp;
	}
	//插入数据
	php->a[php->size] = x;
	php->size++;
	//向上调整//数组，调整元素下标
	AdjustUp(php->a, php->size - 1);
}

//向下调整
void Adjustdown(HpDataType* a, int size, int parent)
{
	//假设法
	int child = parent * 2 + 1;
	while (child < size )//why child < size && child+1<size
	{
		if (child + 1 < size && a[child + 1] < a[child])
		{
			child++;
		}
		//比较
		if (a[child] < a[parent])
		{
			//交换
			Swap(&a[child], &a[parent]);
			parent = child;
			child = child * 2 + 1;
		}
		else//>=
		{
			break;
		}
	}
}
//删除
void HeapPop(HP* php)
{
	assert(php);
	assert(php->size);

	//1.交换
	Swap(&php->a[0], &php->a[php->size - 1]);

	//2.删除
	php->size--;

	//3.向下调整--数组，结束条件size有关，调整的位置parent
	Adjustdown(php->a, php->size, 0);
}

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

	return php->a[0];
}


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

bool HeapEmpty(HP* php)
{
	assert(php);

	return php->size != 0;//!=0是true不为NULL执行   ==0 flase 不执行
}

当然，【大堆】只要改变大小符号即可，如果你不想要改变，可以使用【回调函数】！！ 

🙂感谢大家的阅读，若有错误和不足，欢迎指正！希望本周可以结束【初阶数据结构】

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

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

相关文章

关于谷歌新版调试用具(Chrome Dev Tool )，网络选项(chrome-network)默认开启下拉模式的设置

关于谷歌新版调试用具(Chrome Dev Tool )，网络选项(chrome-network)默认开启下拉模式的设置

今天在使用谷歌浏览器进行调试的时候&#xff0c;打开调试工具网络选项发现过滤不同模式的选项卡不见了&#xff0c;转而变成一个下拉式选项&#xff0c;如下图 这样一来使得切换不同类型查看的时候变得非常不方便&#xff0c;然后网上查了一下发现这个功能谷歌在很早版本就已…
阅读更多...
Mysql 主从库的重新配置

Mysql 主从库的重新配置

1.从库和主库的数据差异实在太大&#xff0c;反复处理数据耗时耗力&#xff0c;不如重做。 2.备份主数据库(命令备份的) usr/local/mysql/bin/mysqldump -h 100.1.4.42 -P 5566 -u root -p 备份数据库 > /mysql/db/备份的名称.sql 3.停止从库复制 登录到MySQL从库&#x…
阅读更多...
腾讯云邀请你参与【腾讯2024技术答人挑战赛】 赢取丰厚的礼品

腾讯云邀请你参与【腾讯2024技术答人挑战赛】 赢取丰厚的礼品

腾讯云邀请你参与【腾讯2024技术答人挑战赛】 赢取丰厚的礼品 2024年 腾讯礼品大派送 保持技术好奇心是程序员构建护城河的重要一环&#xff0c;快来测测你现在的技术知识面在中国程序员中排第几&#xff1f; 参与答题更有iPad、Pico VR游戏机、Switch等、腾讯云官方认证证书好…
阅读更多...
Prometheus+grafana配置监控系统

Prometheus+grafana配置监控系统

使用docker compose安装 方便拓展, 配置信息都放在在 /docker/prometheus 目录下 1.目录结构如下 . ├── conf │ └── prometheus.yml ├── grafana_data ├── prometheus_data └── prometheus_grafana.yaml2.创建目录文件 mkdir /docker/prometheus &&am…
阅读更多...
Leetcode—2670. 找出不同元素数目差数组【简单】

Leetcode—2670. 找出不同元素数目差数组【简单】

2024每日刷题&#xff08;一零七&#xff09; Leetcode—2670. 找出不同元素数目差数组 实现代码 class Solution { public:vector<int> distinctDifferenceArray(vector<int>& nums) {unordered_set<int> s;int n nums.size();vector<int> dif…
阅读更多...
CapCut - 剪映国际版11.0.0

CapCut - 剪映国际版11.0.0

【应用名称】&#xff1a;CapCut - 剪映国际版 【适用平台】&#xff1a;#Android 【软件标签】&#xff1a;#CapCut #剪映国际版 【应用版本】&#xff1a;11.0.0 【应用大小】&#xff1a;231MB 【软件说明】&#xff1a;软件升级更新。目前大家广泛使用的最令人惊叹、最专业…
阅读更多...
linux环境安装git、maven、jenkins等

linux环境安装git、maven、jenkins等

重启 jenkins的命令&#xff1a; systemctl start jenkins 如果没有vim 命令 可以使用 yum install vim 安装 vim git 下载包地址 https://www.kernel.org/pub/software/scm/git/git-2.28.0.tar.gz 1.安装依赖环境&#xff1a; yum install -y curl-devel expat-devel ge…
阅读更多...
2023年03月CCF-GESP编程能力等级认证Python编程二级真题解析

2023年03月CCF-GESP编程能力等级认证Python编程二级真题解析

一、单选题（共15题，共30分） 第1题 以下存储器中的数据不会受到附近强磁场干扰的是（ ）。 A：硬盘 B：U 盘 C：内存 D：光盘 答案：D 第2题 下列流程图，属于计算机的哪种程序结构？（ ） A：顺序结构 B：循环结构 C：分支结构 D：数据结构 答案：C 第3题 以下选…
阅读更多...
C#用正则表达式判断字符串是否纯数字vs用Char.IsDigit 方法遍历字符数组是否纯数字

C#用正则表达式判断字符串是否纯数字vs用Char.IsDigit 方法遍历字符数组是否纯数字

目录 一、使用的方法 1.正则表达式 2.Char.IsDigit 方法 二、源码 1.源代码 2.生成效果 一、使用的方法 1.正则表达式 在程序运行过程中&#xff0c;经常需要用户输入数字信息&#xff0c;如输入员工年龄、工资等。使用正则表达式Regex类的IsMatch方法&#xff0c;可以有…
阅读更多...
2015年苏州大学837复试机试C/C++

2015年苏州大学837复试机试C/C++

2015年苏州大学复试机试 第一题 题目 有36块砖&#xff0c;现在有36个人&#xff0c;男人能搬4块&#xff0c;女人能搬3块&#xff0c;小孩子两人搬一块&#xff0c;求一次搬完这些砖要男人&#xff0c;女人&#xff0c;小孩多少人&#xff1f; 代码 #include <iostrea…
阅读更多...
分析HarmonyOS应用/服务的CPU活动性能

分析HarmonyOS应用/服务的CPU活动性能

CPU Profiler 性能分析是用来分析CPU性能瓶颈的工具&#xff0c;可以实时查看应用/服务的CPU使用率和线程活动&#xff0c;也可以查看记录的方法跟踪数据、方法采样数据和系统跟踪数据的详情。基于CPU性能分析&#xff0c;您可以了解在一段时间内执行了哪些方法&#xff0c;以及…
阅读更多...
Python行定位符

Python行定位符

在Python中&#xff0c;每一行代码都有其特定的位置和作用&#xff0c;而行定位符则是指定或确定代码所在行的一种方法。通过行定位符&#xff0c;开发者可以准确地指定代码的位置&#xff0c;从而对程序进行调试、错误处理等操作。本文将详细介绍Python中常见的行定位符&#…
阅读更多...
【excel转word】excel怎么转换成word？分享两种方法！

【excel转word】excel怎么转换成word？分享两种方法！

Excel文件想要转换成word文档中&#xff0c;直接粘贴复制的话&#xff0c;可能会导致表格格式错乱&#xff0c;那么如何转换才能够保证表格不错乱&#xff1f;今天分享两个方法&#xff0c;excel表格转换为word文件。 方法一&#xff1a; 首先打开excel表格&#xff0c;将表格…
阅读更多...
PyCharm / DataSpell 导入WSL2 解析器，实现GPU加速

PyCharm / DataSpell 导入WSL2 解析器，实现GPU加速

PyCharm / DataSpell 导入WSL2 解析器的实现 Windows的解析器不好么&#xff1f;设置WSL2和实现GPU加速为PyCharm / DataSpell 设置WSL解析器设置Interpreter Windows的解析器不好么&#xff1f; Windows上的解析器的确很方便&#xff0c;也省去了我们很多的麻烦。但是WSL2的解…
阅读更多...
【51单片机系列】中断优先级介绍及使用

【51单片机系列】中断优先级介绍及使用

文章来源&#xff1a;《51单片机原理及应用&#xff08;第3版&#xff09;》5.4节。 51单片机采用了自然优先级和人工设置高、低优先级的策略。 当CPU处理低优先级中断&#xff0c;又发生更高级中断时&#xff0c;此时中断处理过程如下图所示。 一个正在执行的低优先级中断服…
阅读更多...
深度学习(10)-Keras项目详解(递归神经网络)

深度学习(10)-Keras项目详解(递归神经网络)

一.递归神经网络基础概念 递归神经网络(Recursive Neural Network, RNN)可以解决有时间序列的问题&#xff0c;处理诸如树、图这样的递归结构。 CNN主要应用在计算机视觉CV中&#xff0c;RNN主要应用在自然语言处理NLP中。 1.h0&#xff0c;h1.....ht对应的是不同输入得到的中…
阅读更多...
微服务中间件 RabbitMq学习

微服务中间件 RabbitMq学习

1、为什么需要Mq 例如在用户注册业务中&#xff0c;用户注册成功后 需要发注册邮件和注册短信&#xff0c;传统的做法有两种 1.串行的方式&#xff1b;2.并行的方式 &#xff1b; 假设三个业务节点分别使用50ms&#xff0c;串行方式使用时间150ms&#xff0c;并行使用时间10…
阅读更多...
Mybatis 源码系列：领略设计模式在 Mybatis 其中的应用

Mybatis 源码系列：领略设计模式在 Mybatis 其中的应用

文章目录 一、Builder模式二、工厂模式三、单例模式四、代理模式五、组合模式六、模板方式模式七、适配器模式八、装饰器模式九、迭代器模式 虽然我们都知道有23种设计模式&#xff0c;但是大多停留在概念层面&#xff0c;真实开发中很少遇到&#xff0c;Mybatis源码中使用了大…
阅读更多...
企业股权结构API：为金融机构提供全面的企业背景调查服务

企业股权结构API：为金融机构提供全面的企业背景调查服务

摘要 在当今快速变化的商业环境中&#xff0c;金融机构面临着日益复杂的风险管理挑战。为了做出明智的投资和信贷决策&#xff0c;深入了解企业的股权结构和实际控制人信息变得至关重要。企业股权结构API作为一种创新工具&#xff0c;为金融机构提供了一种高效、便捷的途径&am…
阅读更多...
MATLAB知识点：常见的数学运算函数

MATLAB知识点：常见的数学运算函数

​讲解视频&#xff1a;可以在bilibili搜索《MATLAB教程新手入门篇——数学建模清风主讲》。​ MATLAB教程新手入门篇&#xff08;数学建模清风主讲&#xff0c;适合零基础同学观看&#xff09;_哔哩哔哩_bilibili 节选自第2章 大家可以打开本节的配套代码&#xff1a;“cod…
阅读更多...
最新文章

Copyright @ 2022~2023