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

数据结构:堆和二叉树遍历

堆的特征

1.堆是一个完全二叉树

2.堆分为大堆和小堆。大堆:左右节点都小于根节点

小堆:左右节点都大于根节点

堆的应用:堆排序,topk问题

堆排序

堆排序的思路:

1.升序排序,建小堆。堆顶就是这个堆最小的数,堆顶和这个堆的最后一个数换位置,然后再把最后一个数取出,再pop这个数。就得到最小值。像这样每次取一个最小值,再删掉。依次把取出的数放在数组中,就得到升序排序了。

2.降序排序,建大堆。思路同升序一样。

上面说的是向下调整。向下调整就是每次取个数,由于和堆的最后一个数交换了位置,取出之后的二叉树需要调整一下才能成为一个堆。如果是大堆,就比较堆顶的和左右子树,大于它,堆顶和大的那个交换,这样层层交换下去。

如果一共有k层,最坏交换k次,如果是N个节点,就是log(N+1)次。

堆排序就是排N个数嘛,时间复杂度就是O(N*logN),空间复杂度就是O(N)。

向上调整:

向上调整可以应用于尾部插入数。调成一个大堆后停止。

对于一个随机数组,建大堆,向下调整法:

对于一个随机数组建小堆,向上调整法:

topk问题

如何从10000个数中取出最大的50个数?此问题也可以用于:内存空间不够,建堆数量有限,如何在大量的数据中取出前k个最大(小)的数。

答:先取出这些数据中前50(k)个建小堆,剩下的数和堆顶相比,遇到大于堆顶的数就直接替换掉堆顶的数。替换一次,小堆也要向下调整一次,保持它是一个小堆。这样比到最后一个数。就能保持这个小堆是这10000个数中最大的50个了。

如果是取出最小的50个数,那就是建大堆了。遇到比堆顶小的就替换、调整等。

二叉树的遍历

用链表建二叉树。

typedef struct BinaryNode
{int val;struct BinaryNode* left;struct BinaryNode* right;
}BTNode,*pBTNode;

如上述代码所示,树的一个节点存储三个值,一个是它的数据,一个是它指向的左子树指针,一个是指向右子树的指针。如果左子树和右子树都是空,就指向空。

这样由链表构建的一个二叉树。可以通过三种遍历方式来读取整个二叉树的数据。

前序:根----左子树----右子树

中序:左子树----根----右子树

后序:左子树----右子树----根

前中后序的命名是根据访问根的顺序来命名的。以前序遍历来举例:

相关文章:

数据结构:堆和二叉树遍历

堆的特征 1.堆是一个完全二叉树 2.堆分为大堆和小堆。大堆:左右节点都小于根节点 小堆:左右节点都大于根节点 堆的应用:堆排序,topk问题 堆排序 堆排序的思路: 1.升序排序,建小堆。堆顶就是这个堆最小…...

[Halcon学习笔记]在Qt上实现Halcon窗口的字体设置颜色设置等功能

1、 Halcon字体大小设置在Qt上的实现 在之前介绍过Halcon窗口显示文字字体的尺寸和样式,具体详细介绍可回看 (一)Halcon窗口界面上显示文字的字体尺寸、样式修改 当时介绍的设定方法 //Win下QString Font_win "-Arial-10-*-1-*-*-1-&q…...

ArcGis 地图文档

ArcGis官网 https://developers.arcgis.com/labs/android/create-a-starter-app/ Arcgis for android 加载谷歌、高德和天地图 https://blog.csdn.net/qq_19688207/article/details/108125778 AeroMap图层地址: API_KEY: 7e95eae2-a18d-34ce-beaa-894d6a08c5a5 街道图&#xf…...

【C语言】动态内存分配

1、为什么要有动态内存分配 不管是C还是C中都会大量的使用,使用C/C实现数据结构的时候,也会使用动态内存管理。 我们已经掌握的内存开辟方式有: int val 20; //在栈空间上开辟四个字节 char arr[10] { 0 }; //在栈空间…...

算法思想总结:位运算

创作不易,感谢三连支持!! 一、常见的位运算总结 标题 二、位1的个数 . - 力扣(LeetCode) 利用第七条特性:n&(n-1)干掉最后一个1,然后每次都用count去统计&#xff…...

四、HarmonyOS应用开发-ArkTS开发语言介绍

目录 1、TypeScript快速入门 1.1、编程语言介绍 1.2、基础类型 1.3、条件语句 1.4、函数 1.5、类 1.6、模块 1.7、迭代器 2、ArkTs 基础(浅析ArkTS的起源和演进) 2.1、引言 2.2、JS 2.3、TS 2.4、ArkTS 2.5、下一步演进 3、ArkTs 开发实践…...

3 Spring之DI详解

5,DI相关内容 前面我们已经完成了bean相关操作的讲解,接下来就进入第二个大的模块DI依赖注入,首先来介绍下Spring中有哪些注入方式? 我们先来思考 向一个类中传递数据的方式有几种? 普通方法(set方法)构造方法 依赖注入描述了在容器中建…...

Web框架开发-Ajax

一、 Ajax准备知识:json 1、json(Javascript Obiect Notation,JS对象标记)是一种轻量级的数据交换格式 1 2 它基于 ECMAScript (w3c制定的js规范)的一个子集,采用完全独立于编程语言的文本格式来存储和表示数据。 简洁和清晰的层次结构使得 JSON 成为理想的数据交换语言。…...

Python爬虫之urllib库

1、urllib库的介绍 可以实现HTTP请求,我们要做的就是指定请求的URL、请求头、请求体等信息 urllib库包含如下四个模块 request:基本的HTTP请求模块,可以模拟请求的发送。error:异常处理模块。parse:工具模块&#x…...

Docker学习笔记 - 常用命令

目录 基本概念常用命令使用docker compose启动脚本创建自己的image Docker命令文档 1. 下载一个image 从hub.docker.com下载一个image。 docker pull [image name]下载时指定image的tag。 docker pull [image name]:<tag>举例&#xff0c;下载postgre的tag为alpine…...

数学建模(Topsis python代码 案例)

目录 介绍: 模板: 案例: 极小型指标转化为极大型(正向化): 中间型指标转为极大型(正向化): 区间型指标转为极大型(正向化): 标准化处理: 公式: Topsis(优劣解距离法): 公式: 完整代码: 结果: 介绍: 在数学建模中,Topsis方法是一种多准则决策分…...

gateway网关指定路由响应超时时间

gateway网关指定路由响应超时时间 spring:cloud:gateway:httpclient:responseTimeout: 10000这个配置用于设置HttpClient的响应超时时间&#xff0c;单位是毫秒。具体来说&#xff0c;这个配置表示当Gateway向后端服务发出请求后&#xff0c;如果在10秒内没有收到后端服务的响…...

docker 和K8S知识分享

docker知识&#xff1a; 比如写了个项目&#xff0c;并且在本地调试没有任务问题&#xff0c;这时候你想在另外一台电脑或者服务器运行&#xff0c;那么你需要在另外一台电脑或者服务器配置相同的软件&#xff0c;比如数据库&#xff0c;web服务器&#xff0c;必要的插件和库等…...

MySQL--select count(*)、count(1)、count(列名) 的区别你知道吗?

MySQL select count(*)、count(1)、count(列名) 的区别&#xff1f; 这里我们先给出正确结论&#xff1a; count(*)&#xff0c;包含了所有的列&#xff0c;会计算所有的行数&#xff0c;在统计结果时候&#xff0c;不会忽略列值为空的情况。count(1)&#xff0c;忽略所有的列…...

使用verilog设计实现16位CPU及仿真

这是一个简单的16位CPU(中央处理单元)的设计实验。这个CPU包括指令存储器、数据存储器、ALU(算术逻辑单元)、寄存器文件和控制单元。 设计一个简单的16位CPU的实验通常可以分为以下几个步骤: 指令集设计:首先确定CPU支持的指令集架构,包括指令格式、寄存器组织、地址模…...

Python将字符串转换为datetime

有这样一些字符串&#xff1a; 1710903685 20240320110125 2024-03-20 11:01:25 要转换成Python的datetime 代码如下&#xff1a; import functools import re from datetime import datetime, timedelta from typing import Union# pip install python-dateutil from date…...

Vue 3 + TypeScript + Vite的现代前端项目框架

随着前端开发技术的飞速发展&#xff0c;Vue 3、TypeScript 和 Vite 构成了现代前端开发的强大组合。这篇博客将指导你如何从零开始搭建一个使用Vue 3、TypeScript以及Vite的前端项目&#xff0c;帮助你快速启动一个性能卓越且类型安全的现代化Web应用。 Vue 3 是一款渐进式Jav…...

浏览器强缓存和弱缓存的主要区别

浏览器强缓存与弱缓存 浏览器的缓存机制主要分为两种&#xff1a;强缓存与协商缓存&#xff08;也称弱缓存&#xff09;。 强缓存 强缓存是指浏览器在请求一个资源时&#xff0c;不与服务器发生通信&#xff0c;直接从本地缓存中获取资源。如果存在有效的强缓存&#xff0c;…...

深度学习-2.9梯度不稳定和Glorot条件

梯度不稳定和Glorot条件 一、梯度消失和梯度爆炸 对于神经网络这个复杂系统来说&#xff0c;在模型训练过程中&#xff0c;一个最基础、同时也最常见的问题&#xff0c;就是梯度消失和梯度爆炸。 我们知道&#xff0c;神经网络在进行反向传播的过程中&#xff0c;各参数层的梯…...

地宫取宝dfs

分析&#xff1a; 矩阵里的每一个位置都有标记&#xff0c;要求的问题是&#xff1a;有几种方法能完成这个规定。 那么&#xff0c;我们只需要计算从开始(1,1)到最后(n,m)的深度优先搜索中&#xff0c;有几个是满足要求的即为正确答案。 有个要求是&#xff0c;如果一个格子中…...

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖

在前面的练习中&#xff0c;每个页面需要使用ref&#xff0c;onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入&#xff0c;需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...

Golang dig框架与GraphQL的完美结合

将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用&#xff0c;可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器&#xff0c;能够帮助开发者更好地管理复杂的依赖关系&#xff0c;而 GraphQL 则是一种用于 API 的查询语言&#xff0c;能够提…...

【Go】3、Go语言进阶与依赖管理

前言 本系列文章参考自稀土掘金上的 【字节内部课】公开课&#xff0c;做自我学习总结整理。 Go语言并发编程 Go语言原生支持并发编程&#xff0c;它的核心机制是 Goroutine 协程、Channel 通道&#xff0c;并基于CSP&#xff08;Communicating Sequential Processes&#xff0…...

从零实现STL哈希容器:unordered_map/unordered_set封装详解

本篇文章是对C学习的STL哈希容器自主实现部分的学习分享 希望也能为你带来些帮助~ 那咱们废话不多说&#xff0c;直接开始吧&#xff01; 一、源码结构分析 1. SGISTL30实现剖析 // hash_set核心结构 template <class Value, class HashFcn, ...> class hash_set {ty…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

Matlab | matlab常用命令总结

常用命令 一、 基础操作与环境二、 矩阵与数组操作(核心)三、 绘图与可视化四、 编程与控制流五、 符号计算 (Symbolic Math Toolbox)六、 文件与数据 I/O七、 常用函数类别重要提示这是一份 MATLAB 常用命令和功能的总结,涵盖了基础操作、矩阵运算、绘图、编程和文件处理等…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...