当前位置: 首页 > news >正文

二叉树——堆的实现

一.前言

前面我们讲解了二叉树的概念以及二叉树的存储结构:https://blog.csdn.net/yiqingaa/article/details/139224974?spm=1001.2014.3001.5502

今天我们主要讲讲二叉树的存储结构,以及堆的实现。

二.正文

1.二叉树的顺序结构及实现

1.1二叉树的顺序结构

 普通的二叉树是不适合用数组来存储的,因为可能会存在大量的空间浪费。而完全二叉树更适合使用顺序结构存储。现实中我们通常把堆(一种二叉树)使用顺序结构的数组来存储,需要注意的是这里的堆和操作系统虚拟进程地址空间中的堆是两回事,一个是数据结构,一个是操作系统中管理内存的一块区域分段。

1.2堆的概念及结构

如果有一个关键码的集合K = { k₀,k₁,k₂ ,…,k_(n-1)(注意:_()在这里表示()里是下标 ,如我们这里表示的是k的下标是n-1},把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中,并满足:K_(i) <=K_(2*i+1) 且K_(i) <=K_(2*i+2) (K_(i) >=K_(2*i+1) 且 K_(i)>=K_(2*i+2) ) i = 0,1,2…,则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆,根结点最小的堆叫做最小堆或小根堆。

堆的性质:

  1. 堆中某个结点的值总是不大于或不小于其父结点的值。
  2. 堆总是一棵完全二叉树。

值得注意的是:这里我们虽然把它想像成树的形状,但其实我们的底层是数组,我们是通过改变数组,来控制这棵“树”的。

打个比方来说:蚂蚁上树这道菜,这盘菜里面真的有蚂蚁吗?其实没有,只不过是人为想像成的而已。在这里的二叉树也是同样的道理。

 2.堆的实现

2.1堆向下调整算法

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

这里我们给了一个数组。

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

//向下调整算法
void AdjustDown(HPDataType* php,int n ,int parent )//php是数组指针
{int child = parent * 2 + 1;if (php[child] > php[child + 1])child = parent * 2 + 2;while (child < n){if (php[child] < php[parent]){Swap(&(php[child]), &(php[parent]));parent = child;child = parent * 2 + 1;}else{break;}}
}

2.2向上调整算法

 现在我们给出一个数组,逻辑上看做一颗完全二叉树。我们通过从根结点开始的向上调整算法可以把它调整成一个小堆。

我们给出了一个数组:

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

void AdjustUp(HPDataType* php,int child)//向上调整算法
{int parent = (child - 1) / 2;while (child > 0){if (php[child] < php[parent]){Swap(&(php[child]), &(php[parent]));child = parent;parent = (child - 1) / 2;}else{break;}}
}

2.3堆的插入

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

void HPPush(HP* ps,HPDataType x)//堆尾插入数据,ps是我们堆指针
{assert(ps);if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4: ps->capacity * 2;HPDataType* arr = (HPDataType*)realloc(ps->a,sizeof(HPDataType) * newcapacity);if (arr == NULL){perror("realloc false");return;}ps->a = arr;ps->capacity = newcapacity;}ps->a[ps->size] = x;ps->size++;AdjustUp(ps->a,ps->size-1);
}

2.4堆的删除 

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

void HPPop(HP* ps)//删除堆顶数据
{assert(ps);assert(ps->size > 0);Swap(&(ps->a[0]), &(ps->a[ps->size - 1]));ps->size--;AdjustDown(ps->a,ps->size,0);
}

3.堆代码的实现

Heap.h

#pragma once
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<stdbool.h>
typedef int HPDataType;
struct Heap
{HPDataType* a;int size;int capacity;
};
typedef struct Heap HP;
void HPInit(HP* ps);//堆的初始化
void HPDestroy(HP* ps);//堆的删除void HPPush(HP* ps, HPDataType x);//堆尾插入数据
void HPPop(HP* ps);//删除堆顶数据HPDataType HPTop(HP* ps);//取出堆顶数据
bool HPEmpty(HP* ps);//判断堆是否为空void Swap(HPDataType* a, HPDataType* b);//交换两个数据
void AdjustUp(HPDataType* php, int child);//向上调整算法
void AdjustDown(HPDataType* php, int n, int parent);//向下调整算法
int HPSize(HP* ps);//返回堆的有效数据个数
void HPSort(HPDataType* php, int n);//堆排序

Heap.c 

#include"Heap.h"
void HPInit(HP* ps)//堆初始化实现
{assert(ps);ps->a = NULL;ps->size = ps->capacity = 0;}void HPDestroy(HP* ps)//堆销毁实现
{assert(ps);free(ps->a);ps->a = NULL;ps->size = ps->capacity = 0;
}void Swap(HPDataType* a,HPDataType* b)//两个数据的交换
{HPDataType tmp =*a;*a = *b;*b = tmp;
}void AdjustUp(HPDataType* php,int child)//向上调整算法
{int parent = (child - 1) / 2;while (child > 0){if (php[child] < php[parent]){Swap(&(php[child]), &(php[parent]));child = parent;parent = (child - 1) / 2;}else{break;}}
}void HPPush(HP* ps,HPDataType x)//堆尾插入数据
{assert(ps);if (ps->size == ps->capacity){int newcapacity = ps->capacity == 0 ? 4: ps->capacity * 2;HPDataType* arr = (HPDataType*)realloc(ps->a,sizeof(HPDataType) * newcapacity);if (arr == NULL){perror("realloc false");return;}ps->a = arr;ps->capacity = newcapacity;}ps->a[ps->size] = x;ps->size++;AdjustUp(ps->a,ps->size-1);
}
void AdjustDown(HPDataType* php,int n ,int parent )//向下调整算法
{int child = parent * 2 + 1;if (php[child] > php[child + 1])child = parent * 2 + 2;while (child < n){if (php[child] < php[parent]){Swap(&(php[child]), &(php[parent]));parent = child;child = parent * 2 + 1;}else{break;}}
}
void HPPop(HP* ps)//删除堆顶数据
{assert(ps);assert(ps->size > 0);Swap(&(ps->a[0]), &(ps->a[ps->size - 1]));ps->size--;AdjustDown(ps->a,ps->size,0);
}
bool HPEmpty(HP* ps)//判断堆是否为空
{assert(ps);if (ps->size == 0){return true;}return false;
}
HPDataType HPTop(HP* ps)//取出堆顶数据
{assert(ps);assert(ps->size > 0);return ps->a[0];
}
HPDataType HPSize(HP* ps)//返回堆有效数据个数
{assert(ps);return ps->size;
}
void HPSort(HPDataType* php,int n)//堆排序
{//降序 建小堆//升序 建大堆//建堆的第一种方法/*for (int i = 1; i < n; i++){AdjustUp(php, i);}*///建堆的第二种方法:for (int i = (n - 1 - 1) / 2; i < n; i++)//(n-1-1)/2是为了找最后一个数据的父亲{AdjustDown(php, n, i);}int end = n - 1;while (end > 0){Swap(&(php[0]), &(php[end]));AdjustDown(php, end, 0);end--;}
}

test.c 

#include"Heap.h"
void test01()
{HP hp;HPInit(&hp);HPPush(&hp, 6);HPPush(&hp, 2);HPPush(&hp, 3);HPPush(&hp, 4);HPPush(&hp, 10);HPPush(&hp, 9);HPPush(&hp, 7);HPPop(&hp);printf("%d\n", HPTop(&hp));printf("%d\n", HPSize(&hp));
//	HPDestroy(&hp);
}
void test02()
{int arr[] = { 1,2,6,4,5,8,9,7 };HPSort(&arr,sizeof(arr)/sizeof(int));
}
int main()
{//test01();test02();return 0;
}

值得注意的是test.c是本人为了测试各函数是否正常而写出来的。

三.结言

 堆的分享就到这了。觉得对自己有帮助的同学,可不可以给个三连。

好啦,同学们我们下期再见,拜拜喽。

相关文章:

二叉树——堆的实现

一.前言 前面我们讲解了二叉树的概念以及二叉树的存储结构&#xff1a;https://blog.csdn.net/yiqingaa/article/details/139224974?spm1001.2014.3001.5502 今天我们主要讲讲二叉树的存储结构&#xff0c;以及堆的实现。 二.正文 1.二叉树的顺序结构及实现 1.1二叉树的顺序…...

【Spring】DynamicDataSourceHolder 动态数据源切换

【Spring】DynamicDataSourceHolder 动态数据源切换 常见场景常见工具一、AbstractRoutingDataSource1.1、 定义 DynamicDataSourceHolder1.2、 配置动态数据源1.3、 在Spring配置中定义数据源1.4、在业务代码中切换数据源 二、Dynamic Datasource for Spring Boot2.1. 添加依赖…...

LeeCode 3165 线段树

题意 传送门 LeeCode 3165 不包含相邻元素的子序列的最大和 题解 考虑不含相邻子序列的最大和&#xff0c;在不带修改的情况下容易想到&#xff0c;以最后一个元素是否被选取为状态进行DP。从线性递推的角度难以处理待修改的情况。 从分治的角度考虑&#xff0c;使用线段树…...

修改元组元素

自学python如何成为大佬(目录):https://blog.csdn.net/weixin_67859959/article/details/139049996?spm1001.2014.3001.5501 场景模拟&#xff1a;伊米咖啡馆&#xff0c;由于麝香猫咖啡需求量较大&#xff0c;库存不足&#xff0c;店长想把它换成拿铁咖啡。 实例08 将麝香猫…...

【模版方法设计模式】

文章目录 模板方法设计模式模板方法的设计原则模板方法设计模式组成部分代码实现抽象类实现具体实现类执行 模板方法设计模式 模版方法设计模式&#xff08;Template Method Pattern&#xff09;是一种行为设计模式&#xff0c;它定义了一个操作中的算法骨架&#xff0c;而将一…...

rust语言初识

程序设计实践课上水一篇ing 来源&#xff1a;rust基础入门-1.初识rust-酷程网 (kucoding.com) rust作为一名新兴语言&#xff0c;与go又有些许不同&#xff0c;因为它的目标是对标系统级开发&#xff0c;也就是C、C这两位在编程界的位置。比如我们最常用的windows系统&#x…...

知识图谱数据预处理笔记

知识图谱数据预处理笔记 0. 引言1. 笔记1-1. \的转义1-2. 特殊符号的清理1-3. 检查结尾是否正常1-4. 检查<>是否存在1-5. 两端空格的清理1-6. 检查object内容长时是否以<开始 0. 引言 最近学习知识图谱&#xff0c;发现数据有很多问题&#xff0c;这篇笔记记录遇到的…...

Unity面试八股文之基础篇

文章目录 前言1. Unity的生命周期加载第一个场景Editor在第一次帧更新之前帧之间更新顺序协程销毁对象时退出时 2. Unity 协程和线程,进程的区别3. 本地坐标系 世界坐标系4. 碰撞器和触发器的区别后话 前言 开设这个栏目的博文会写一些有关unity的面试题目&#xff0c;在面试的…...

HTTPS能否避免流量劫持?如何实现HTTPS

在当今数字化时代&#xff0c;网站安全已经成为企业和个人的头等大事。随着网络犯罪和数据泄露的增加&#xff0c;保护您的网站免受潜在威胁比以往任何时候都更加重要。网站安全的一个关键组成部分是HTTPS&#xff0c;它代表着安全的超文本传输协议。HTTPS是标准HTTP协议的安全…...

簡述Vue 2.0 响应式数据的原理

Vue 2.0 响应式数据的原理主要基于以下几个关键点&#xff1a; 数据劫持与Object.defineProperty&#xff1a; Vue 2.0 使用 Object.defineProperty 方法来劫持对象的属性&#xff0c;为其添加 getter 和 setter 方法。当数据被访问或修改时&#xff0c;这些 getter 和 setter …...

Kafka线上集群部署方案怎么做?no.6

专栏前面几期内容&#xff0c;我分别从Kafka的定位、版本的变迁以及功能的演进等几个方面循序渐进地梳理了Apache Kafka的发展脉络。通过这些内容&#xff0c;我希望你能清晰地了解Kafka是用来做什么的&#xff0c;以及在实际生产环境中该如何选择Kafka版本&#xff0c;更快地帮…...

vscode 的 AI 协助插件 Tabnine / Codeium

4.1、Tabnine 描述&#xff1a;Tabnine 是一款基于深度学习技术的代码自动补全工具。该插件支持多种编程语言&#xff0c;包括 Python、JavaScript、TypeScript、Java 和 Go 等。它可以根据您输入的代码段和上下文信息&#xff0c;预测并推荐可能的代码补全选项&#xff0c;从而…...

Flutter 中的 OutlineButton 小部件:全面指南

Flutter 中的 OutlineButton 小部件&#xff1a;全面指南 在Flutter的Material Design组件库中&#xff0c;OutlineButton是一个用于创建带边框的扁平按钮的小部件。这种按钮通常用于次要操作或在需要强调其他按钮的情况下使用。本文将为您提供一个全面的指南&#xff0c;帮助…...

Kubernetes可视化界面之DashBoard

1.1 DashBoard Kubernetes Dashboard 是 Kubernetes 集群的一个开箱即用的 Web UI&#xff0c;提供了一种图形化的方式来管理和监视 Kubernetes 集群中的资源。它允许用户直接在浏览器中执行许多常见的 Kubernetes 管理任务&#xff0c;如部署应用、监控应用状态、执行故障排查…...

Docker学习(4):部署web项目

一、部署vue项目 在home目录下创建项目目录 将打包好的vue项目放入该目录下&#xff0c;dist是打包好的vue项目 在项目目录下&#xff0c;编辑default.conf 内容如下&#xff1a; server {listen 80;server_name localhost; # 修改为docker服务宿主机的iplocation / {r…...

驱动开发中引入私有数据的原因

系列文章目录 驱动开发中引入私有数据的原因 驱动开发中引入私有数据的原因 系列文章目录驱动开发中引入私有数据的原因 驱动开发中引入私有数据的原因 驱动开发中引入私有数据&#xff08;Private Data&#xff09;概念主要是为了解决以下几个关键问题&#xff1a; 1.多设备支…...

删除edge浏览器文本框储存记录值以及关闭自动填充

当我们点击输入框时总会出现许多以前输入过的信息。 一、删除edge浏览器文本框储存记录值 1、首先按下↓键选中你想删除的信息 二、关闭自动填充。 1、在地址栏输入edge://wallet/settings跳转到以下界面 2、往下滑找到 全部取消即可...

mysql事务 事务并发问题 隔离级别 以及原理

mysql事务 简介&#xff1a;事务是一组操作的集合&#xff0c;它是一个不可分割的工作单位&#xff0c;事务会把所有的操作作为一个整体一起向系统提交或撤销操作请求&#xff0c;即这些操作要么同时成功&#xff0c;要么同时失败。 事务四大特性 原子性&#xff08;Atomici…...

Android 性能为王时代SparseArray和HashMap一争高下

文章目录 一、SparseArray 源码分析1. **类定义和构造函数**2. **基本方法**2.1 put(int key, E value)2.2 get(int key)2.3 delete(int key)2.4 removeAt(int index)2.5 gc()2.6 size()2.7 keyAt(int index) 和 valueAt(int index) 3. **辅助方法**3.1 binarySearch() 二、使用…...

学术图表的基本配色方法

不论是商业图表还是专业图表&#xff0c;图表的配色都极其关键。图表配色主要有彩色和黑白两种配色方案。刘万祥老师曾提出&#xff1a; “在我看来&#xff0c;普通图表与专业图表的差别&#xff0c;很大程度就体现在颜色运用上。” 对于科学图表&#xff0c;大部分国内的期…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

在Ubuntu24上采用Wine打开SourceInsight

1. 安装wine sudo apt install wine 2. 安装32位库支持,SourceInsight是32位程序 sudo dpkg --add-architecture i386 sudo apt update sudo apt install wine32:i386 3. 验证安装 wine --version 4. 安装必要的字体和库(解决显示问题) sudo apt install fonts-wqy…...

视觉slam十四讲实践部分记录——ch2、ch3

ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...

人机融合智能 | “人智交互”跨学科新领域

本文系统地提出基于“以人为中心AI(HCAI)”理念的人-人工智能交互(人智交互)这一跨学科新领域及框架,定义人智交互领域的理念、基本理论和关键问题、方法、开发流程和参与团队等,阐述提出人智交互新领域的意义。然后,提出人智交互研究的三种新范式取向以及它们的意义。最后,总结…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

从“安全密码”到测试体系:Gitee Test 赋能关键领域软件质量保障

关键领域软件测试的"安全密码"&#xff1a;Gitee Test如何破解行业痛点 在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的"神经中枢"。从国防军工到能源电力&#xff0c;从金融交易到交通管控&#xff0c;这些关乎国计民生的关键领域…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...