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

【数据结构】败者树的建树与比较过程

文章目录

    • 前置知识
      • 归并段
    • 建树过程
    • 比较过程
    • 疑问
      • 为什么比较次数减少了?
      • 如果某个归并段的元素一直获胜,没有元素了怎么办?
        • 处理方法 1
        • 处理方法 2

前置知识

归并段

  • 外部排序算法通常用于处理大规模数据,其中数据量远超过计算机内存的容量。由于内存无法一次性容纳全部数据,因此需要将数据划分为较小的片段进行排序,在排序过程中将这些片段合并成一个有序的序列
  • 这些归并段内部是有序的,各个归并段之间无序
  • 如图,有 3 个归并段,内部升序
    在这里插入图片描述

建树过程

  • 假设有 5 个节点,给这些节点编号
    在这里插入图片描述

  • 17 是 0 号节点,5 是 1 号节点,…,15 是 4 号节点

  • 为每个节点创建一个根节点,根节点的值是其编号,叶子节点是值
    在这里插入图片描述

  • 从子树中任意挑选两个子树的根节点进行比较,比较对应的值,假设比较规则是:值小的胜出
    本例中,初始有 5 棵子树

  • 比较顺序是任意的,假设根节点为 0 和 1 对应子树进行比较,取出根节点对应的值,5 < 17,5 胜出

    • 除去两棵子树的根节点后,胜者的根节点作为两棵子树的爷节点,败者的根节点作为两棵子树的父节点
    • 即 0 作为父节点,1 作为爷节点

    在这里插入图片描述

  • 比较根节点为 3 和 4 对应子树,取出根节点对应的值,15 < 29,15 胜出
    3 作为父节点,4 作为爷节点
    在这里插入图片描述

  • 比较根节点为 1 和 2 对应的子树,5 < 10,5 胜出
    1 作为爷节点,2 作为父节点
    在这里插入图片描述

  • 比较根节点为 1 和 4 对应的子树,5 < 15,5 胜出
    1 作为爷节点,4 作为 父节点
    在这里插入图片描述

  • 可以看出,根节点是 1,其对应的值是 5,也就是{17, 5, 10, 29, 15} 中的最小值,共比较 4 次
    败者树构建完成

比较过程

  • 将根节点对应的值进行输出,假设编号 1 所在的归并段还有元素需要比较,是 44

  • 败者树需要调整,将根节点重新和编号 1 对应的值进行组合
    在这里插入图片描述

  • 根节点为 0 和 1 的子树进行比较,17 < 44,17 胜出
    0 作为爷节点,1 作为父节点
    在这里插入图片描述

  • 根节点为 0 和 2 的子树进行比较,10 < 17,10 胜出

    2 作为爷节点,0 作为父节点在这里插入图片描述

  • 根节点为 2 和 4 的子树进行比较,10 < 15,10 胜出

    2 作为爷节点,4 作为父节点

    在这里插入图片描述

  • 可以看出,根节点是 2,其对应的值是 10,也就是{17, 44, 10, 29, 15} 中的最小值,共比较 3 次,比建树时找到最小值所需的比较次数(5次)少

疑问

为什么比较次数减少了?

  • 在刚才的例子中,44 没有和 4 的右子树进行比较,这是为什么呢?
    在这里插入图片描述
    • 败者树中,两棵子树的合并规则是:胜者根节点做爷节点,败者做父节点
      因此,编号 3 是败者,编号 4 是胜者

    • 新节点 x 只需要和胜者 y 比较即可

      • 若 x < y,那么 x 可以做根节点,而 y 做父节点
      • 反之 y 做根节点,而 x 做父节点
    • 换句话说,在设定的比较规则中(值小的获胜),我们只关心获胜者(谁是最小的),而不关心节点比哪些节点大

      • 有 2 个集合 A,B,我们想找到两个集合的最小值
        A 集合的最小值是 x
        B 集合的最小值是 y

        显然,要选出最小值,只要比较 x 和 y 即可,若 x < y,那么 x 就是 A 和 B 中最小的,y 比 A 中的哪些元素小,我们并不关心在这里插入图片描述

如果某个归并段的元素一直获胜,没有元素了怎么办?

处理方法 1
  • 记录归并段的元素个数,若某个归并段没有元素,则在输出其根节点对应的值后,移除这课子树

  • 编号 1 对应的归并段没有元素了,那么输出 5,并移除 5 对应的子树,移除后的败者树被破坏了
    在这里插入图片描述

  • 0 和 2 需要重新比较
    在这里插入图片描述

  • 2 和 4 重新比较
    在这里插入图片描述

  • 败者树又构建好了(ヾ(•ω•`)o)
    在这里插入图片描述

处理方法 2
  • 可以填充一个“最大值”,保证所有元素都比最大值小,那么这个最大值就不会在接下来的比较中胜出

  • 1 对应的 5 输出,而 1 合并的是 2 和 4

在这里插入图片描述

  • 假设 999 是最大的值了,类似方法 1,调整一下败者树的结构

在这里插入图片描述
2 对应的 10 是 {17, 999, 10, 29, 15} 中的最小值

相关文章:

【数据结构】败者树的建树与比较过程

文章目录 前置知识归并段 建树过程比较过程疑问为什么比较次数减少了&#xff1f;如果某个归并段的元素一直获胜&#xff0c;没有元素了怎么办&#xff1f;处理方法 1处理方法 2 前置知识 归并段 外部排序算法通常用于处理大规模数据&#xff0c;其中数据量远超过计算机内存的…...

GlobalMapper---dem生成均匀分布的网格,或者均匀分布的点高程点

1打开DEM数据。点击工具栏上的Open Data File(s)按钮&#xff0c;打开DEM数据 2点击【Create Grid】按钮 3生成点 4导出格式xyz 5南方cass展点 6过滤抽稀...

k8s系列文章一:安装指南

前言 k8s是docker的升级版&#xff0c;可用于docker集群配置管理微服务 一、更新ubuntu系统版本 sudo apt update sudo apt upgrade二、添加GPG密钥(阿里源) 尽管我不知道gpg是个什么东西&#xff0c;反正跟着做就完了 curl https://mirrors.aliyun.com/kubernetes/apt/do…...

Pod 进阶

目录 1、资源限制 1.1 官网示例 1.2 CPU 资源单位 1.3 内存 资源单位 2、健康检查&#xff1a;又称为探针&#xff08;Probe&#xff09; 2.1 探针的三种规则 2.2 Probe支持三种检查方法 2.3 官网示例 3、扩展 pod的状态 3.1 Container生命周期 1、资源限制 当定义…...

Proteus仿真--12864LCD显示计算器键盘按键实验(仿真文件+程序)

本文主要介绍基于51单片机的12864LCD液晶显示电话拨号键盘按键实验&#xff08;完整仿真源文件及代码见文末链接&#xff09; 仿真图如下 本设计主要介绍计算器键盘仿真&#xff0c;按键按下后在12864液晶上显示对应按键键值 仿真运行视频 Proteus仿真--12864LCD显示计算器…...

pam_radius库的使用

一. 前言 我们知道&#xff0c;linux pam库是一系列的库&#xff0c;用于处理一些应用程序的认证工作&#xff0c;比如login程序。但是默认的pam库只是用于本地认证&#xff0c;也就是认证的用户名和密码存储在本机上。如果需要远程认证&#xff0c;比如向radius服务器认证&…...

qt6:无法使用setFontColor

问题描述 跟着C开发指南视频学习&#xff0c;但是发现无论是直接使用ui设计&#xff0c;还是纯代码都无法实现变更字体颜色的功能。图中显示&#xff0c;点击颜色控件后&#xff0c;文本框的文字加粗、下划线、斜体等才能设置&#xff0c;但是无法变更颜色。 此文提醒qt sty…...

竞赛 深度学习疫情社交安全距离检测算法 - python opencv cnn

文章目录 0 前言1 课题背景2 实现效果3 相关技术3.1 YOLOV43.2 基于 DeepSort 算法的行人跟踪 4 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &#x1f6a9; **基于深度学习疫情社交安全距离检测算法 ** 该项目较为新颖&#xff0c;适合作为竞赛…...

无声的世界,精神科用药并结合临床的一些分析及笔记(十)

目录 回 “ 家 ” 克服恐惧 奥沙西泮 除夕 酒与药 警告 离别 回 “ 家 ” 她的锥切手术进行的很顺利&#xff0c;按计划继续返回安定医院调节心理状态&#xff0c;病友们都盼着我们回“家”。当我俩跨入病区&#xff0c;大家都涌过来帮我们大包小包的拎着行李&#xff0…...

构建强大的Web应用之Django详解

引言&#xff1a; Django是一个功能强大且灵活的Python Web框架&#xff0c;它提供了一套完整的工具和功能&#xff0c;帮助开发者快速构建高效的Web应用。本篇文章将带您逐步了解Django的基本概念和使用方法&#xff0c;并通过实际的代码案例&#xff0c;帮助您从零开始构建自…...

Linux 之搭建 arm 的 qemu 模拟器

目录 1. Linux 之搭建 arm 的 qemu 模拟器 1. Linux 之搭建 arm 的 qemu 模拟器 OS: kali 1. 安装交叉编译工具、GDB 和 QEMU # sudo apt-get install qemu debootstrap qemu-user-static # sudo apt-get install qemu-system-arm # sudo apt-get install gdb-multiarch //支持…...

uinapp微信小程序隐私政策授权

&#x1f680; 隐私弹窗效果图&#xff1a; 1、启用隐私相关功能在manifest.json文件中配置 usePrivacyCheck: true "mp-weixin" : {"__usePrivacyCheck__" : true, },2、创建组件 <template><view><!-- 隐私政策弹窗 --><uni-popu…...

使用Java工作流简单介绍

本人详解 作者:王文峰,参加过 CSDN 2020年度博客之星,《Java王大师王天师》 公众号:JAVA开发王大师,专注于天道酬勤的 Java 开发问题中国国学、传统文化和代码爱好者的程序人生,期待你的关注和支持!本人外号:神秘小峯 山峯 转载说明:务必注明来源(注明:作者:王文峰…...

数字媒体技术基础之:ICC 配置文件

ICC 配置文件&#xff08;也称为 ICC 色彩配置文件或 ICC 色彩描述文件&#xff09;是由国际色彩联盟&#xff08;International Color Consortium, ICC&#xff09;制定的一种标准文件格式&#xff0c;用于在不同的设备和软件之间保持颜色的一致性。 ICC 配置文件包含有关设备…...

解析SD-WAN组网方式及应用场景,全面了解典型案例

随着企业业务高速发展&#xff0c;跨区域开展业务首要解决的难题是构建各站点能互联互通的网络&#xff0c;然而目前大多数企业在广域网优化的问题上依旧碰壁&#xff0c;主要原因是企业广域网面临的挑战并不能马上得到解决。 传统网络互联方案无论是IPsec还是专线&#xff0c…...

中小学智慧校园电子班牌管理系统源码

智慧校园云平台电子班牌系统&#xff0c;利用先进的云计算技术&#xff0c;将教育信息化资源和教学管理系统进行有效整合&#xff0c;实现基础数据共享、应用统一管理。借助全新的智能交互识别终端和移动化教育管理系统&#xff0c;以考勤、课表、通知、家校互通等功能为切入点…...

日常踩坑-[sass]Error: Expected newline

在学习sass的时候&#xff0c;运行时发现报错 经过网上冲浪知道&#xff0c;原来在声明语言的时候 lang 不能声明为 sass &#xff0c;而是 scss ,这就有点坑了 原因&#xff1a; scss是sass3引入进来的&#xff0c;scss语法有"{}“,”;"而sass没有&#xff0c;所以…...

UI设计感蓝色商务数据后台网站模板源码

蓝色商务数据后台网站模板是一款适合网站模板下载。提示&#xff1a;本模板调用到谷歌字体库&#xff0c;可能会出现页面打开比较缓慢。 演示下载 qnziyw点cn/wysc/qdmb/20852点html...

二、计算机组成原理与体系结构

&#xff08;一&#xff09;数据的表示 不同进制之间的转换 R 进制转十进制使用按权展开法&#xff0c;其具体操作方式为&#xff1a;将 R 进制数的每一位数值用 Rk 形式表示&#xff0c;即幂的底数是 R &#xff0c;指数为 k &#xff0c;k 与该位和小数点之间的距离有关。当…...

MySQL-sql的优化

表的设计优化索引优化SQL语句优化主从复制、读写分离分库分表 表的设计优化(参考阿里开发手册) 比如设置合适的数值(tinyint int bigint)&#xff0c;要根据实际情况选择 比如设置合适的字符串类型(char和varchar) char定长效率高&#xff0c;varchar可变长度&#xff0c;效…...

【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型

摘要 拍照搜题系统采用“三层管道&#xff08;多模态 OCR → 语义检索 → 答案渲染&#xff09;、两级检索&#xff08;倒排 BM25 向量 HNSW&#xff09;并以大语言模型兜底”的整体框架&#xff1a; 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后&#xff0c;分别用…...

在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module

1、为什么要修改 CONNECT 报文&#xff1f; 多租户隔离&#xff1a;自动为接入设备追加租户前缀&#xff0c;后端按 ClientID 拆分队列。零代码鉴权&#xff1a;将入站用户名替换为 OAuth Access-Token&#xff0c;后端 Broker 统一校验。灰度发布&#xff1a;根据 IP/地理位写…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

学习STC51单片机31(芯片为STC89C52RCRC)OLED显示屏1

每日一言 生活的美好&#xff0c;总是藏在那些你咬牙坚持的日子里。 硬件&#xff1a;OLED 以后要用到OLED的时候找到这个文件 OLED的设备地址 SSD1306"SSD" 是品牌缩写&#xff0c;"1306" 是产品编号。 驱动 OLED 屏幕的 IIC 总线数据传输格式 示意图 …...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

智能仓储的未来:自动化、AI与数据分析如何重塑物流中心

当仓库学会“思考”&#xff0c;物流的终极形态正在诞生 想象这样的场景&#xff1a; 凌晨3点&#xff0c;某物流中心灯火通明却空无一人。AGV机器人集群根据实时订单动态规划路径&#xff1b;AI视觉系统在0.1秒内扫描包裹信息&#xff1b;数字孪生平台正模拟次日峰值流量压力…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

Java + Spring Boot + Mybatis 实现批量插入

在 Java 中使用 Spring Boot 和 MyBatis 实现批量插入可以通过以下步骤完成。这里提供两种常用方法&#xff1a;使用 MyBatis 的 <foreach> 标签和批处理模式&#xff08;ExecutorType.BATCH&#xff09;。 方法一&#xff1a;使用 XML 的 <foreach> 标签&#xff…...

PHP 8.5 即将发布:管道操作符、强力调试

前不久&#xff0c;PHP宣布了即将在 2025 年 11 月 20 日 正式发布的 PHP 8.5&#xff01;作为 PHP 语言的又一次重要迭代&#xff0c;PHP 8.5 承诺带来一系列旨在提升代码可读性、健壮性以及开发者效率的改进。而更令人兴奋的是&#xff0c;借助强大的本地开发环境 ServBay&am…...