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

二叉树------最小堆,最大堆。

什么是最小堆:

        堆是一种二叉树,最小堆中所有父亲节点的值都要比自己的子节点的值要小。而根节点称为堆顶。根据定义我们可以得到堆中最小元素就在堆顶。(节点左上角是编号,内部是元素值)

        


         假设该图中的堆顶元素是24呢?显然不符合最小堆的定义,那么我们要怎么处理呢?

        假设7号节点的值是1呢?显然不符合最小堆的定义,那么我们要怎么处理呢?

如何调整堆:

        

        在该图中我们先让 24 与左孩子的值比较发现 左孩子比自己小,再看右孩子,发现右孩子比左孩子还小,于是1号节点值和3号节点值交换。然后再看3号节点的左孩子和右孩子值都比 24 小,但是6号节点值更小,所以3号节点值24和6号节点值交换,完成最小堆的向下调整。

        

        该图我们先让7号节点与3号节点比较,发现5 比 1大 然后交换两个节点的值,3号节点再和1号节点比较发现2比1大,然后交换节点的值,完成了最小堆的向上调整。

        如果忘记了怎么存储二叉树,参考这篇博文:树------二叉树-CSDN博客

具体代码:

void down(int i)//i为需要调整的节点编号。
{
    int t, flag = 0;

    while (2 * i <= n && flag == 0)//判断当前节点是否有左子树。
    {
        if (arr[i] > arr[2 * i])
            t = 2 * i;
        else
            t = i;//如果左子树比本节点小,记录该节点下标,否则记录该节点下标。
        if (2 * i + 1 <= n)//如果有右子树。
            if (arr[2 * i + 1] < arr[t])
                t = 2 * i + 1;//确定最终交换值的节点下标。

        if (t != i)
        {
            swap(i, t);
            i = t;
        }//如果最终交换值的下标不等于本节点,证明需要交换值。
        else
            flag = 1;//如果没有交换,证明本节点调整完毕,退出循环。
    }
}

void up(int i)//向上调整函数。
{
    int flag = 0;

    if (i == 1)//如果已经在堆顶,不需要调整。
        return;

    while (i != 1 && flag == 0)
    {
        if (arr[i] < arr[i / 2])
            swap(i, i / 2);//如果本节点小于父亲节点,交换值,负责退出循环。
        else
            flag = 1;

        i /= 2;//节点编号调整为父亲节点。
    }
}

void swap(int i, int j)
{
    int k = arr[i];
    arr[i] = arr[j];
    arr[j] = k;
}//交换函数。

注意点:

        最大堆和最小堆差不多,最大堆定义是任何父亲节点都要比子节点要大,至于如何调整,可以改变以上代码的大小判断符号。

        另外关于昨天的 Bellman-Ford算法的优化的答案博文因为某些原因今天无法更新(其实是我忘记写了。。。。。。),明天再为大家呈上。该算法博文链接如下。

        图论------贝尔曼-福德(Bellman-Ford)算法-CSDN博客

相关文章:

二叉树------最小堆,最大堆。

什么是最小堆&#xff1a; 堆是一种二叉树&#xff0c;最小堆中所有父亲节点的值都要比自己的子节点的值要小。而根节点称为堆顶。根据定义我们可以得到堆中最小元素就在堆顶。&#xff08;节点左上角是编号&#xff0c;内部是元素值&#xff09; 假设该图中的堆顶元素是24呢&a…...

预约功能的知识整理

前置知识 如果项目为小程序的开发项目中&#xff1a; 我们确定数据库中有的字段有: 预约人姓名、手机号、家人名称、预约时间 根据我们的经定一表必须要有的6个字段&#xff1a; 主键、创建时间、修改时间、创建人、修改人、备注 使用我们现在有的字段为&#xff1a; 主键…...

Linux的常用操作-02

一&#xff1a;Linux的系统目录结构 /bin bin是ary的缩写&#xff0c;这个目录存放着最经常用的命令 /boot&#xff1a;这里存放的是启动Linux时使用的一些核心文件&#xff0c;包括一些连接文件以及镜像文件。 /dev&#xff1a;dev是Device(设备)的缩写,该目录下存放的是Lin…...

Android Studio 连接手机进行调试

总所周知&#xff0c;Android Studio里的虚拟手机下载后又大又难用。不如直接连手机用。本篇文章主要内容为Android Studio怎么连接手机进行程序调试。 1. 在AndroidSDK中下载google USB Driver: 2. 连接手机&#xff1a; 进入电脑设备管理器界面。并点开便携设备&#xff0c…...

Vue3项目创建及相关配置

Vue是一种用于构建用户界面的JavaScript框架。它采用了一种称为MVVM&#xff08;Model-View-ViewModel&#xff09;的架构模式。 MVVM是一种将用户界面与业务逻辑和数据分离的设计模式。它包括三个部分&#xff1a; Model&#xff08;模型&#xff09;&#xff1a;表示应用程序…...

【Python】Python中一些有趣的用法

Python是一种非常灵活和强大的编程语言&#xff0c;它有很多有趣的用法&#xff0c;以下是一些例子&#xff1a; 一行代码实现FizzBuzz&#xff1a; print(\n.join([FizzBuzz[i%3*4:i%5*8:-1] or str(i) for i in range(1, 101)]))使用列表推导式生成斐波那契数列&#xff1a; …...

RCE复现问题和研究

目录 先了解一些常见的知识点 PHP常见命令执行函数 call_user_func eval&#xff08;&#xff09; call_user_func_array array_filter 实战演练&#xff08;RCE&#xff09;PHP Eval函数参数限制在16个字符的情况下 &#xff0c;如何拿到Webshell&#xff1f; 1、长度…...

MySQL中的索引——适合创建索引的情况

1.适合创建索引的情况 1、字段的数值有唯一性的限制 2、频繁作为 WHERE 查询条件的字段 某个字段在 SELECT 语句的 WHERE 条件中经常被使用到&#xff0c;那么就需要给这个字段创建索引了。尤其是在数据量大的情况下&#xff0c;创建普通索引就可以大幅提升数据查询的效率。 …...

5款在线伪原创改写软件,智能改写文章效果好

在这个信息爆炸的时代&#xff0c;内容创作变得愈发重要&#xff0c;而对于创作者来说&#xff0c;有时需要一些得力的伪原创改写工具来辅助我们更好地改写出高质量的内容。今天我要和大家分享5款令人惊喜的在线伪原创改写软件&#xff0c;它们以出色的智能改写效果&#xff0c…...

opencv-python图像增强四:多曝光融合(方法一)

文章目录 一、简介&#xff1a;二、多曝光融合方案&#xff1a;三、算法实现步骤3.1 读取图像与曝光时间&#xff1a;3.2 计算响应曲线并合并3.3 色调映射 四&#xff1a;整体代码实现五&#xff1a;效果 一、简介&#xff1a; 在摄影和计算机视觉领域&#xff0c;高动态范围&…...

Qt 实战(9)窗体 | 9.2、QDialog

文章目录 一、QDialog1、基本概念2、常用特性2.1、模态与非模态2.2、数据交互 3、总结 前言&#xff1a; Qt框架中的QDialog类是一个功能强大且灵活的对话框控件&#xff0c;广泛应用于各种GUI&#xff08;图形用户界面&#xff09;应用程序中&#xff0c;用于处理用户输入、消…...

Spring 事务机制

1. 引言 1.1 什么是事务 事务是由用户定义的一系列操作序列所组成的最小工作单元&#xff1b;这些操作要么全部完成&#xff0c;要么全部不完成&#xff0c;是一个不可分割的工作单元。常见于数据库中的并发控制和数据一致性处理场景。 1.2 事务的特性 事务具有以下特性&am…...

Android 13 GMS 内置壁纸

如图&#xff0c;原生系统上&#xff0c;设备上的壁纸 显示系统内置壁纸。如果没有添加内置壁纸&#xff0c;就显示默认的壁纸。点击进去就是预览页面 扩展下&#xff0c;默认壁纸在 frameworks/base/core/res/res/drawable-sw720dp-nodpi/default_wallpaper.png frameworks/b…...

【LeetCode】234. 回文链表

回文链表 题目描述&#xff1a; 给你一个单链表的头节点 head &#xff0c;请你判断该链表是否为回文链表。如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 示例 1&#xff1a; 输入&#xff1a;head [1,2,2,1] 输出&#xff1a;true示例 2&#…...

零基础学会机器学习,到底要多久?

这两天啊&#xff0c;有不少朋友和我说&#xff0c;想学机器学习&#xff0c;但是之前没有基础&#xff0c;不知道能不能学得会。 首先说结论&#xff0c;只要坚持&#xff0c;就能学会&#xff0c;但是一定不能三天打鱼两天晒网&#xff0c;要持之以恒&#xff0c;至少每隔两…...

视频汇聚/安防监控综合平台EasyCVR接入海康私有协议EHOME显示失败是什么原因?

安防监控/视频综合管理平台/视频集中存储/磁盘阵列EasyCVR视频汇聚平台&#xff0c;支持多种视频格式和编码方式&#xff08;H.264/H.265&#xff09;&#xff0c;能够轻松对接各类前端监控设备&#xff0c;实现视频流的统一接入与集中管理。安防监控EasyCVR平台支持多种流媒体…...

Qt解析XML

背景 本来想解析VS的项目配置文件(*.vcxproj)&#xff0c;配合cppclean来发现多余的#incldue。 结果发现低估了难度&#xff0c;VS会间接引入许多目录。 略有不甘&#xff0c;暂且作为一个解析XML文件的示例。 代码 VSProjectParser.h #include <QVector> #include…...

PwnLab: init-文件包含、shell反弹、提权--靶机渗透思路讲解

Vulnhub靶机链接回【PwnLab】 首页有一个登录框 image-20240807124822770 他没有验证码&#xff0c;我们试试暴力破解 image-20240807122743025 开始爆破了&#xff0c;全部失败&#xff0c;哈哈哈 image-20240807122851001 nmap全端口扫描试试 image-20240807131408315 有…...

OpenCV—二值化Threshold()、adaptiveThreshold()

cv2.threshold() c&#xff1a;double cv::threshold ( InputArray src, OutputArray dst, double thresh, double maxval, int type ) (注&#xff1a;源图片, 目标图, 阈值, 填充色, 阈值类型) python:cv.threshold(src,thresh, maxval, type[, dst]) src&#xff1a;源图片…...

第二天:java面向对象编程(OOP)

第二天&#xff1a;java面向对象编程&#xff08;OOP&#xff09; 1. 深入理解OOP四大特性 封装&#xff08;Encapsulation&#xff09;&#xff1a;学习如何将数据&#xff08;属性&#xff09;和操作数据的方法&#xff08;行为&#xff09;组合成一个独立的单元&#xff0…...

Python|GIF 解析与构建(5):手搓截屏和帧率控制

目录 Python&#xff5c;GIF 解析与构建&#xff08;5&#xff09;&#xff1a;手搓截屏和帧率控制 一、引言 二、技术实现&#xff1a;手搓截屏模块 2.1 核心原理 2.2 代码解析&#xff1a;ScreenshotData类 2.2.1 截图函数&#xff1a;capture_screen 三、技术实现&…...

Docker 离线安装指南

参考文章 1、确认操作系统类型及内核版本 Docker依赖于Linux内核的一些特性&#xff0c;不同版本的Docker对内核版本有不同要求。例如&#xff0c;Docker 17.06及之后的版本通常需要Linux内核3.10及以上版本&#xff0c;Docker17.09及更高版本对应Linux内核4.9.x及更高版本。…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

.Net框架,除了EF还有很多很多......

文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...

Mac软件卸载指南,简单易懂!

刚和Adobe分手&#xff0c;它却总在Library里给你写"回忆录"&#xff1f;卸载的Final Cut Pro像电子幽灵般阴魂不散&#xff1f;总是会有残留文件&#xff0c;别慌&#xff01;这份Mac软件卸载指南&#xff0c;将用最硬核的方式教你"数字分手术"&#xff0…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序

一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...

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

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

【C语言练习】080. 使用C语言实现简单的数据库操作

080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...