当前位置: 首页 > 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;大部分国内的期…...

synchronized 学习

学习源&#xff1a; https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖&#xff0c;也要考虑性能问题&#xff08;场景&#xff09; 2.常见面试问题&#xff1a; sync出…...

VB.net复制Ntag213卡写入UID

本示例使用的发卡器&#xff1a;https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

vue3 定时器-定义全局方法 vue+ts

1.创建ts文件 路径&#xff1a;src/utils/timer.ts 完整代码&#xff1a; import { onUnmounted } from vuetype TimerCallback (...args: any[]) > voidexport function useGlobalTimer() {const timers: Map<number, NodeJS.Timeout> new Map()// 创建定时器con…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

selenium学习实战【Python爬虫】

selenium学习实战【Python爬虫】 文章目录 selenium学习实战【Python爬虫】一、声明二、学习目标三、安装依赖3.1 安装selenium库3.2 安装浏览器驱动3.2.1 查看Edge版本3.2.2 驱动安装 四、代码讲解4.1 配置浏览器4.2 加载更多4.3 寻找内容4.4 完整代码 五、报告文件爬取5.1 提…...

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)

题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...

ui框架-文件列表展示

ui框架-文件列表展示 介绍 UI框架的文件列表展示组件&#xff0c;可以展示文件夹&#xff0c;支持列表展示和图标展示模式。组件提供了丰富的功能和可配置选项&#xff0c;适用于文件管理、文件上传等场景。 功能特性 支持列表模式和网格模式的切换展示支持文件和文件夹的层…...

对象回调初步研究

_OBJECT_TYPE结构分析 在介绍什么是对象回调前&#xff0c;首先要熟悉下结构 以我们上篇线程回调介绍过的导出的PsProcessType 结构为例&#xff0c;用_OBJECT_TYPE这个结构来解析它&#xff0c;0x80处就是今天要介绍的回调链表&#xff0c;但是先不着急&#xff0c;先把目光…...