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

数据结构初阶 —— 树(堆)

目录

一,堆

堆的概念

向下调整法(数组)

向上调整法(数组)

堆的创建(建堆)

堆的实现 


一,堆

堆的概念

  • 如有个关键码的集合K={k_{0}k_{1}k_{2},...,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、...,则称为小堆(大堆);

小堆

  • k_{i}<=k_{2*i+1} 且 k_{i}<=k_{2*i+2} ,即所有节点小于等于孩子;
  • 根节点最小,叫做最小堆或小根堆;

大堆

  • k_{i}>=k_{2*i+1} 且 k_{i}>=k_{2*i+2} ,即所有节点大于等于孩子;
  • 根节点最大,叫做最大堆或大根堆;

堆的性质

  • 堆中某个节点的值,总是不大于或不小于其父节点的值;
  • 根一定是最值(最大值或最小值);
  • 堆总是一颗完全二叉树,适合顺序结构存储;

向下调整法(数组)

  • 将数组看做为一颗完全二叉树,可使用向下调整法创建堆;
  • 前提条件为,此二叉树的左右子树需是一个堆,只有根节点不满足堆要求;
  • 从根开始,与左右子节点中的最小值,比较并交换,依次类推,直到比父亲大或到叶子节点终止;
  • 时间复杂度,O(logN);
  • 注,向上调整法类似;
int array[] = {27,15,19,18,28,34,65,49,25,37};

//向下调整法,小堆
void Swap(int* px, int* py)
{int tmp = *px;*px = *py;*py = tmp;
}void AdjustDown(int* arr, int n, int parent)
{int child = 2 * parent + 1;//无孩子节点或父亲小于孩子,即终止while (child < n){if (child + 1 < n && arr[child + 1] < arr[child])child++;if (arr[parent] > arr[child]){Swap(arr + parent, arr + child);parent = child;child = 2 * parent + 1;}elsebreak;}
}

向上调整法(数组)

//向上调整法
void AdjustUp(int* arr, int child)
{int parent = (child - 1) / 2;//大堆//根节点或父亲大于孩子,即终止while (child > 0){if (arr[parent] < arr[child]){Swap(arr + parent, arr + child);child = parent;parent = (child - 1) / 2;}elsebreak;}
}

堆的创建(建堆)

  •  即对数据如数组(可看为完全二叉树),将其构建为堆;
  • 方法为,从倒数第一个非叶子节点的子树开始调整,直到根节点为止;
  • 即每次调整时,使用向下调整法;
  • 建堆时间复杂度,O(N),下面有证明;
  • 注,也可使用向上调整法建堆,但初始化堆的个别元素位置可能不一样;
int arr[] = {1,5,3,8,7,6}; 
//建堆-向下调整法
void Heap(int* arr, int n)
{int i = (n - 1 - 1) / 2; //最后节点的父节点for (i; i >= 0; i--){AdjustDown(arr, n, i);}
}
//建堆-向上调整法
void Heap(int* arr, int n)
{int i = 1; for (i; i < n; i++){AdjustUp(arr, i);}
}

建堆时间复杂度

堆排序  

  • 升序,建大堆(将最大的数换到最后,在将剩下的数向下调整下,选出次大数,依次类推);
  • 降序,建小堆(将最小的数换到最后,在将剩下的数向下调整下,选出次小数,依次类推);
  • 整体的时间复杂度,O(N*logN);
  • 如升序建小堆(或降序建大堆)的话,选出最值后,需在继续建堆(O(N)),效率较低,还不如直接遍历,建堆的价值未体现;
//建堆排序
void HeapSort(int* arr, int n)
{//建堆 - O(N)int i = (n - 1 - 1) / 2; //最后节点的父节点for (i; i >= 0; i--){AdjustDown(arr, n, i);}//排序 - O(N*log(N))int end = n - 1;while (end){Swap(arr, arr + end);AdjustDown(arr, end, 0);end--;}
}

堆的实现 

//堆
typedef int HPDataType;typedef struct Heap
{HPDataType* data;int size;int capacity;
}Heap;//初始化
void HeapInit(Heap* php, HPDataType* arr, int n);//释放销毁
void HeapDestroy(Heap* php);//插入数据并保持堆
void HeapPush(Heap* php, HPDataType* x);//删除堆顶数据并保持堆
void HeapPop(Heap* php);//返回堆顶数据
HPDataType HeapTOP(Heap* php);//返回堆节点个数
int HeapSize(Heap* php);//判断释放为空
bool HeapEmpty(Heap* php);

注:完整接口实现代码路径https://gitee.com/napoleoncode/start-code/tree/master/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/06_Heap

TOP-K问题

  • 直接排序,O(N*log(N));
  • 建个N个数的堆,并取出前K个数,O(N+K*log(N));
  • 建个K个数的小堆,然后将剩下的数依次与堆顶比较,大即入堆,最后此堆即为最大的K个数,O(N*log(K));(如N非常大内存不够,前两种方法即适用了);
  • 注,通常K远小于N;
//TOP-K
void TOPK(int* arr, int n, int k)
{Heap hp;//建堆HeapInit(&hp, arr, k);int i = k;for (i; i < n; i++){//替换if (HeapTop(&hp) > arr[i]){HeapPop(&hp);HeapPush(&hp, arr[i]);}}HeapPrint(&hp);HeapDestroy(&hp);
}

相关文章:

数据结构初阶 —— 树(堆)

目录 一&#xff0c;堆 堆的概念 向下调整法&#xff08;数组&#xff09; 向上调整法&#xff08;数组&#xff09; 堆的创建&#xff08;建堆&#xff09; 堆的实现 一&#xff0c;堆 堆的概念 如有个关键码的集合K{&#xff0c;&#xff0c;&#xff0c;...&#xf…...

一文看懂低代码,5分钟从入门到原理全搞定

全球低代码市场已经走过了近20年&#xff0c;中国低代码市场近5年经历了百花齐放的广泛探索阶段&#xff0c;更旺盛的市场需求逐步在被激发。现在&#xff0c;让我们按下暂停键&#xff0c;看看这些产品给我们呈现了低代码市场一幅怎样的百景图。 低代码平台简介 广义上的低代…...

MetaERP系统主要干什么的,华为自研ERP的路子是否可以效仿?

近日&#xff0c;华为成功研发出自主可控的MetaERP系统&#xff0c;并完成了对旧有ERP系统的替换。该系统采用全栈自主可控技术&#xff0c;基于华为欧拉操作系统、GaussDB等根技术&#xff0c;采用云原生架构、元数据多租架构、实时智能技术等&#xff0c;提高业务效率&#x…...

自动驾驶——离散LQR的黎卡提方程Riccati公式推导与LQR工程化

1.LQR Question Background 之前写过连续系统的黎卡提方程Riccati推导&#xff0c;但是考虑到实际工程落地使用的是离散系统&#xff0c;于是又进行了离散黎卡提方程Riccati的公式推导。 2.Proof of Riccati Equation Formula for Discrete Systems 工程化落地&#xff0c;就…...

28.Mybatis的入门

目录 一、Mybatis的入门。 &#xff08;1&#xff09;Mybatis的简介。 &#xff08;2&#xff09;Mybatis的快速入门。 &#xff08;2.1&#xff09;快速入门。 &#xff08;2.2&#xff09;UserMapper.xml文件。 &#xff08;2.3&#xff09;sqlMapConfig.xml文件。 …...

Android Jetpack 从使用到源码深耕【ViewModel从实践到原理 】(三)

上文,我们通过简单的ViewModel使用源码入手,对其源码进行阅读,原理进行了简单总结,简单来说,ViewModel是通过Activity的onRetainNonConfigurationInstance 与 getLastNonConfigurationInstance的自动调用,实现了 ViewModel数据的存储和恢复,数据存储在ViewModelStore的m…...

什么性格的人适合报考环境科学类专业?高考选专业

环境科学类专业包括有&#xff1a;环境科学与工程&#xff0c;环境工程&#xff0c;环境科学&#xff0c;环境生态工程&#xff0c;环保设备工程&#xff0c;资源环境科学&#xff0c;水质科学与技术。 环境对于未来是一个极其重要的方向&#xff0c;需要学生具备一定的科学素…...

Python中的异常处理机制可以帮助程序员在程序运行过程中遇到错误时进行处理

Python中的异常处理机制可以帮助程序员在程序运行过程中遇到错误时进行处理&#xff0c;防止程序崩溃或出现不可预测的错误。 Python中的异常处理使用try-except语句。try语句块包含可能会出现异常的代码&#xff0c;而except语句块则定义了出现异常时应该执行的操作。下面是一…...

TCP之报文格式解析

TCP网络协议是较常用的&#xff0c;也基本上都会接触&#xff0c;那么来简单了解下它吧。TCP 是一种面向连接的、可靠的传输协议&#xff0c;它能够将数据分成一些小块&#xff0c;并通过 Internet 进行传输。在 TCP 中&#xff0c;数据被分割成一些称为 TCP 报文段&#xff08…...

qemu-基础篇(二)——裸机 arm 程序环境搭建

文章目录 测试代码makefile运行 qemu调试 qemuGDB 常用命令 裸机篇系列文章主要用于熟悉 arm 汇编及处理器结构 测试代码 _start:ldr r0, 0X020C4068 /* CCGR0 */ldr r1, 0XFFFFFFFF str r1, [r0]ldr r0, 0X020C406C /* CCGR1 */str r1, [r0]ldr r0, 0X020C4070 …...

JSP+SQL基于JSP的学生信息管理系统(源代码+论文+答辩PPT)

随着学校规模的不断扩大&#xff0c;学生数量急剧增加&#xff0c;有关学生的各种信息也成倍增长。面对如此庞大的信息量&#xff0c;开发学生信息管理系统来提高学生管理工作的效率就成为必然。通过该系统&#xff0c;可以做到信息的规范管理、科学统计和快速查询&#xff0c;…...

docker上部署程序后无法连接数据库的问题

咱就是说&#xff0c;这个问题差点给我劝退docker。下面说下环境情况。 装了个javaweb程序容器&#xff0c;装了个数据库容器&#xff0c;javaweb容器就是链接不上数据库。 咱也是跟着菜鸟教程的容器互联步骤简历网络链接&#xff1a; 并且启动时增加--networkxxx 都加入到了…...

Ucore lab4

实验目的 了解内核线程创建/执行的管理过程了解内核线程的切换和基本调度过程 实验内容 练习一&#xff1a;分配并初始化一个进程控制块 1.内核线程及管理 内核线程是一种特殊的进程&#xff0c;内核线程与用户进程的区别有两个&#xff1a;内核线程只运行在内核态&#x…...

AI失业潮来袭,某些部门裁员过半

历史的车轮滚滚向前&#xff0c;每次生产力的大幅跃进&#xff0c;都会造成一批失业潮。想当年&#xff0c;纺纱机的出现让无数手工作坊的织布师傅失业。如今&#xff0c;在AI技术的催化下&#xff0c;同样的事正在互联网行业的各个领域重演。 疯狂的裁员浪潮 “AI15秒做的&am…...

git 撤销add/commit,以及更换源命令

前言&#xff1a;主要是为了自己方便记录&#xff0c;省的每次都查找一下这些命令 1、当我们只是想撤回commit&#xff0c;保留add .的时候&#xff0c;可以用下方代码 git reset --soft HEAD^ 2、当我们想撤回commit以及add .的时候&#xff0c;可以用下方代码 git reset…...

3dMax需要什么样的硬件环境才能更好的工作?

3dMax官方给出了系统要求的列表 ,可用于帮助确保系统中的硬件能够与他们的软件一起工作。但是,这个“系统要求”列表只涵盖了运行软件所需硬件的最基本知识,而不是实际提供最佳性能的硬件。由于这些列表的不一致程度,我们花时间进行测试以确定运行 3dMax 的最佳硬件。基于…...

python-使用Qchart总结4-绘制多层柱状图

1、上代码 import sysfrom PyQt5.QtChart import QChart, QChartView, QBarCategoryAxis, QValueAxis, QBarSeries, QBarSet from PyQt5.QtGui import QPainter, QColor from PyQt5.QtWidgets import QMainWindow, QApplicationfrom untitled import Ui_MainWindow #从生成好的…...

Java学习笔记-02

目录 流程控制语句 分支语句 循环语句 Random随机数 数组 方法 流程控制语句 分为顺序语句(从上到下&#xff0c;依次执行)&#xff0c;分支语句(if&#xff0c;else...)和循环语句(for&#xff0c;while&#xff0c;do...while) 分支语句 分为if与switch两大类 单分…...

中通快递财报预测:中通快递2023年收入和利润将大幅下降

来源&#xff1a;猛兽财经 作者&#xff1a;猛兽财经 市场对中通快递2023年的预测 卖方虽然预测中通快递&#xff08;ZTO&#xff09;在2023年的表现会很不错&#xff0c;但他们也预计中通快递今年的财务业绩将不会像去年那样好。 根据S&P Capital IQ的数据&#xff0c;卖…...

Javaweb | 状态管理:Session、Cookie

&#x1f497;wei_shuo的个人主页 &#x1f4ab;wei_shuo的学习社区 &#x1f310;Hello World &#xff01; 状态管理 问题引入 HTTP协议是无转态的&#xff0c;不能保存提交的信息如果用户发来一个新的请求&#xff0c;服务器无法知道它是否与上次的请求联系对于那些需要多次…...

Redux

Redux 作用 集中式管理react、vue、angular等应用中多个组件的状态&#xff0c;是一个库&#xff0c;不单单可用于react&#xff0c;只是更多的用于react中 模型图 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-AaFD3raR-1682994570670)(img/re…...

Nacos配置中心的详解与搭建

Namespace 简介 用于进行租户粒度的配置隔离&#xff0c;不同的命名空间下&#xff0c;可以存在相同的 Group 或 Data ID 的配置 配置Namespace 点击nacos的命名空间——点击新建命名空间 开发环境【dev】测试环境【test】正式环境【prod】 DataID 简介 Data ID 通常用于…...

Java入门教程||Java 封装||Java 接口

Java 封装 在面向对象程式设计方法中&#xff0c;封装&#xff08;英语&#xff1a;Encapsulation&#xff09;是指&#xff0c;一种将抽象性函式接口的实作细节部份包装、隐藏起来的方法。 封装可以被认为是一个保护屏障&#xff0c;防止该类的代码和数据被外部类定义的代码…...

微软开源AI修图工具让老照片重现生机

GitHub - microsoft/Bringing-Old-Photos-Back-to-Life: Bringing Old Photo Back to Life (CVPR 2020 oral) 支持划痕修复&#xff0c;以及模型训练。 Old Photo Restoration (Official PyTorch Implementation) Project Page | Paper (CVPR version) | Paper (Journal vers…...

什么是 Docker?它能用来做什么?

文章目录 什么是云计算&#xff1f;什么是 Docker&#xff1f;虚拟化技术演变特点架构镜像&#xff08;Image&#xff09;仓库&#xff08;Registry &#xff09;容器&#xff08;Container&#xff09; 应用场景 什么是云计算&#xff1f; 云计算是一种资源的服务模式&#x…...

生成器的创建方式(py编程)

1. 生成器的介绍 根据程序员制定的规则循环生成数据&#xff0c;当条件不成立时则生成数据结束。数据不是一次性全部生成处理&#xff0c;而是使用一个&#xff0c;再生成一个&#xff0c;可以节约大量的内存。 2. 创建生成器的方式 生成器推导式yield 关键字 生成器推导式…...

百胜中国:未来将实现强劲增长

来源&#xff1a;猛兽财经 作者&#xff1a;猛兽财经 收入分析与未来展望 在过去的三年里&#xff0c;百胜中国&#xff08;YUMC&#xff09;的收入一直受到疫情导致的旅行限制和封锁的影响。为了应对疫情造成的业务中断&#xff0c;该公司开始专注于外卖业务&#xff0c;并将…...

【Celery】任务Failure或一直超时Pending

编写背景 task进入队列后&#xff0c;部分任务出现Failure或者一直Pending,且业务代码没有报错。 运行环境 celery配置 from celery import Celery broker redis://:127.0.0.1:6379/1 backend redis://:127.0.0.1:6379/2 app Celery(brokerbroker,backendbackend,includ…...

【严重】VMware Aria Operations for Logs v8.10.2 存在反序列化漏洞(CVE-2023-20864)

漏洞描述 VMware Aria Operations for Logs前身是vRealize Log Insight&#xff0c;VMware用于处理和管理大规模的日志数据产品。 VMware Aria Operations for Logs 8.10.2版本中存在反序列化漏洞&#xff0c;具有 VMware Aria Operations for Logs 网络访问权限的未经身份验…...

java实现乘法的方法

我们都知道&#xff0c;乘法运算的核心思想就是两个数相乘&#xff0c;如果能将乘法运算转化成一个加数的运算&#xff0c;那么这个问题就很容易解决。比如我们要实现23的乘法&#xff0c;首先需要定义两个变量&#xff1a;2和3。我们将这两个变量定义为一个变量&#xff1a;2x…...