当前位置: 首页 > 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;如果一个格子中…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

【论文笔记】若干矿井粉尘检测算法概述

总的来说&#xff0c;传统机器学习、传统机器学习与深度学习的结合、LSTM等算法所需要的数据集来源于矿井传感器测量的粉尘浓度&#xff0c;通过建立回归模型来预测未来矿井的粉尘浓度。传统机器学习算法性能易受数据中极端值的影响。YOLO等计算机视觉算法所需要的数据集来源于…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

网络编程(UDP编程)

思维导图 UDP基础编程&#xff08;单播&#xff09; 1.流程图 服务器&#xff1a;短信的接收方 创建套接字 (socket)-----------------------------------------》有手机指定网络信息-----------------------------------------------》有号码绑定套接字 (bind)--------------…...