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

【数据结构】哈夫曼树

哈夫曼树

路径长度:从树中一个结点到另一个结点之间的分支构成这两个节点之间的路径,路径上的分支数目称为路径长度

树的带权路径长度:树中所有叶子结点的带权路径长度之和,通常记为WPL= ∑ k = 1 n w k l k \sum^{n}_{k=1}w_kl_k k=1nwklk

带权路径长度最小的二叉树称为最优二叉树哈夫曼树

注意

哈夫曼树不一定是完全二叉树

书中一定没有度为1的结点

树中权值最小的两个结点一定是兄弟

包含n个叶子节点的哈夫曼树共有2n-1个结点

包含n棵树的森林要经过n-1次合并才能形成哈夫曼树,共形成n-1个新结点,且度为2

树中任意非叶子节点的权值一定不小于下一层任意结点的权值

哈夫曼树的构造

哈夫曼算法:

  1. 根据给定的权值构成n棵二叉树的森林,每棵树只有一个带权为wi的根节点
  2. 在森林中选取两棵根节点权值最小的树作为左右子树,构造一棵新的二叉树,且设置新的二叉树的根节点的权值为其左右子树的权值和
  3. 在森林中删除这两棵树,同时将新得到的二叉树加入森林中
  4. 重复(2)(3),直到森林中只有一棵树为止,这棵树即为哈夫曼树(重复第二步时不一定选用新树)

哈夫曼树的实现

采用顺序存储结构

typedef struct{int weight;int parent,lch,rch;
}HTNode,*HTree;
void CreateHuffmanTree(HuffmanTree HT,int n){if(n<=1)return;m=2*n-1;//数组共2n-1个元素HT=new HTNode[m+1];//0号单元未用,HT[m]表示根节点for(i=1;i<=m;i++){	//将2n-1个元素的lch、rch、parent置为0HT[i].lch=0;HT[i].rch=0;HT[i].parent=0;}for(i=1;i<=n;++i)cin>>HT[i].weight;//输入前n个元素的weight值//初始化结束,下面开始建立哈夫曼树for(i=n+1;i<=m;i++){	//合并产生n-1个结点——构造Huffman树Select(HT,i-1,s1,s2);//在HT[k]中选择两个双亲域为0,且权值最小的结点,并返回它们在HT中的序号s1和s2HT[s1].parent=i;HT[s2].parent=i;	//表示从F中删除s1、s2HT[i].lch=s1;	HT[i].rch=s2;	//s1,s2分别作为i的左右孩子HT[i].weight=HT[s1].weight+HT[s2].weight;//i的权值为左右孩子权值之和}
}

哈夫曼编码

将编码设计为不等长的二进制编码,让代传字符中出现次数较多的字符采用较短的编码

前缀编码:任一个字符的编码都不是另一个字符的字符的编码的前缀

构造哈夫曼编码:

  1. 将字符出现的频率作为权值,构建哈夫曼树
  2. 从根节点出发,左分支标记0,右分支标记1
  3. 从根节点出发,到叶子节点,路过的所有分支的编码组合起来,就是哈夫曼编码

相关文章:

【数据结构】哈夫曼树

哈夫曼树 路径长度&#xff1a;从树中一个结点到另一个结点之间的分支构成这两个节点之间的路径&#xff0c;路径上的分支数目称为路径长度 树的带权路径长度&#xff1a;树中所有叶子结点的带权路径长度之和&#xff0c;通常记为WPL ∑ k 1 n w k l k \sum^{n}_{k1}w_kl_k …...

网络安全法-网络运行安全

第三章 网络运行安全 第一节 一般规定 第二十一条 国家实行网络安全等级保护制度。网络运营者应当按照网络安全等级保护制度的要求&#xff0c;履行下列安全保护义务&#xff0c;保障网络免受干扰、破坏或者未经授权的访问&#xff0c;防止网络数据泄露或者被窃取、篡改&…...

188-下翻便携式6U CPCI工控机箱

一、板卡概述 下翻式CPCI便携工控机,系统采用6u cpci背板结构,1个系统槽,7个扩展槽, 满足对携带的需求,可装标准6U8槽CPCI主板,8个扩展槽, 满足客户对空间扩展的需求.可宽温服务的工作产品,15高亮度液晶显示屏,超薄88键笔记本键盘,触摸式鼠标,加固型机箱结构,使它能够适应各种复…...

【0362】Postgres内核 XLogReaderState readBuf 有完整 XLOG page header 信息 ? ( 7 )

上一篇: 【0361】Postgres内核 page_read 读取所请求数据长度(至少 short page header)( 6 ) 文章目录 1. 检查 page_read 返回值 readLen2. 根据 readBuf 计算 XLogPageHeader 大小2.1 验证 XLOG Page header2.2 更新 XLogReaderState 读取状态信息1. 检查 page_read 返回…...

调度系统:Luigi 的主要特性和功能

Luigi 是一个开源的 Python 工作流管理工具&#xff0c;用于构建批处理作业管道&#xff0c;特别适用于数据工程领域。它被设计用来编排任务和处理任务间的依赖关系&#xff0c;支持自动化复杂的 ETL 流程、数据分析、模型训练等任务。 Luigi 的主要特性和功能&#xff1a; 任…...

GO泛型

泛型是goSDK1.18版本之后才引入的新特性&#xff0c;即C中的模板。 为什么要有泛型&#xff1f; 我们现在要写一个两数相加的函数&#xff0c;相加的逻辑很简单&#xff0c;但是如果传入不同的类型&#xff0c;那么我们就需要再写一个函数&#xff0c;定义不同的参数类型&#…...

【笔记】C语言转C++

网课链接&#xff1a;【C语言 转 C 简单教程】 https://www.bilibili.com/video/BV1UE411j7Ti/?p27&share_sourcecopy_web&vd_source4abe1433c2a7ef632aeed6a3d5c0b22a 网课老师B站id:别喷我id 视频总时长&#xff1a;01:55:27 以下笔记是我通过此网课整理 建议先…...

Python 单例模式工厂模式和classmethod装饰器

前言&#xff1a; Python作为面向对象的语言&#xff0c;显然支持基本的设计模式。也具备面向对象的语言的基本封装方法&#xff1a;属性、方法、继承、多态等。但是&#xff0c;做为强大的和逐渐发展的语言&#xff0c;python也有很多高级的变种方法&#xff0c;以适应更多的…...

源码编译构建LAMP

源码编译构建LAMP 文章目录 源码编译构建LAMPLAMPDISCUZ论坛 1.安装编译工具等2.apache3.mysql4.php5.部署论坛网站6.其他6.其他 LAMPDISCUZ论坛 1.安装编译工具等 安装说明&#xff1a; 配置yum源 从阿里云下载新的配置文件 curl -o /etc/yum.repos.d/CentOS-Base.repo htt…...

如何让verilog支持二维数组,三维数组作为I/O ports

写在前面 先看看verilog中的一维数组&#xff0c;二维数组&#xff0c;三维数组长啥样&#xff1f; wire [31:0]data1;//一维数组 wire [31:0]data2 [0:15];//二维数组 wire [31:0]data3 [0:15][0:15];//三维数组众所周知&#xff0c;verilog只支持一维数组作为I/O ports&…...

字符编码讲解(C#)

在学习和编码的过程中&#xff0c;极容易遇到如下概念&#xff0c;他们有些是字符编码&#xff0c;有些是涉及的相关概念&#xff0c;接下来我将围绕下面的熟悉又陌生的概念做详细解释&#xff0c;并且梳理其之间的关系 UTF8&#xff0c; Unicode &#xff0c;ASCII&#xff0…...

Unreal Engine 中的UI界面开发

推荐的使用方式 轻量级 HUD&#xff1a;使用 Canvas 绘制简单的文本、调试信息或基础 UI&#xff08;如准星、血量条等&#xff09;。 复杂 UI&#xff1a;使用 UMG&#xff08;Unreal Motion Graphics&#xff09;和 Slate 进行布局和交互&#xff0c;避免手动管理 Canvas 绘制…...

聚类及Python下实现 K-means 算法

聚类 聚类是无监督学习中的一种重要方法&#xff0c;旨在将数据集中相似的数据对象划分到同一个簇中&#xff0c;使得不同簇之间的数据对象差异尽可能大。在大数据环境下&#xff0c;聚类可以帮助挖掘数据中的隐藏结构和模式&#xff0c;应用场景十分广泛&#xff0c;比如在客…...

【中间件开发】Redis基础命令详解及概念介绍

文章目录 前言一、Redis相关命令详解及原理1.1 string、set、zset、list、hash1.1.1 string1.1.2 list1.1.3 hash1.1.4 set1.1.5 zset 1.2 分布式锁的实现1.3 lua脚本解决ACID原子性1.4 Redis事务的ACID性质分析 二、Redis协议与异步方式2.1 Redis协议解析2.1.1 redis pipeline…...

分布式文件存储 - - - MinIO从入门到飞翔

MinIO从入门到飞翔 文章目录 MinIO从入门到飞翔 0、前言1、分布式文件系统2、MinIO 介绍3、 MinIO安装&#xff08;docker&#xff09;4、基本概念5、通过代码上传文件到MinIO6、封装MinIO为starter7、在其他项目中集成封装好的模块 0、前言 对象存储是一种数据存储架构&a…...

Cadence学习笔记 1 原理图库绘制

基于Cadence 17.4&#xff0c;四层板4路HDMI电路 目录 一、原理图绘制及封装制作 1、原理图库绘制简介 一、原理图绘制及封装制作 1、原理图库绘制简介 File--Change Product&#xff0c;选择OrCAD Capture CIS。绘制原理图和原理图库都是用CIS完成 更改界面颜色&#xff1a…...

Unity 制作一个视频播放器(打包后,可在外部编辑并放置新的视频)

效果展示&#xff1a; 在这里&#xff0c;我把视频名称&#xff08;Json&#xff09;和对应的视频资源都放在了StreamingAssets文件夹下&#xff0c;以便于打包后&#xff0c;客户还可以自己在外部增加、删除、修改对应的视频资料。 如有需要&#xff0c;请联细抠抠。...

python爬虫--小白篇【爬虫实践】

一、前言 1.1、王者荣耀皮肤爬虫 根据王者荣耀链接&#xff0c;将王者荣耀的全部英雄的全部皮肤图片爬取保存到本地。经过分析得到任务的三个步骤&#xff1a; 根据首页全部英雄列表连接获取全部英雄的名称hero_name以及对应的hero_id&#xff1b;根据单个英雄的hero_name和h…...

CountDownLatch阻塞后countDown未执行会如何?

背景 某项目封装了 Kafka 消费者 API&#xff0c;根据传递的消费者线程数&#xff0c;创建 N 个消费者线程同时消费对应 topic 的数据&#xff0c;并在线程启动后收集到全局列表中&#xff0c;方便在程序调用 stop 流程时逐个停止。 主控类在创建 Kafka 消费线程时使用了 Cou…...

《MySQL 查询进阶:复杂查询语句的魅力》

一、引言 MySQL 的复杂查询语句就像是一把神奇的钥匙&#xff0c;能够打开数据世界的大门&#xff0c;展现出数据的无限魅力。本文将带你深入探索 MySQL 查询进阶技巧&#xff0c;从常用查询到子查询&#xff0c;再到视图的运用&#xff0c;让你领略复杂查询语句的强大功能。 …...

Vue解决跨域问题

要解决 Vue 项目的跨域问题并通过 vue.config.js 配置代理&#xff0c;可以按照以下步骤修改 vue.config.js 文件。你提供的代码大部分已经正确&#xff0c;只需要做一些格式上的调整。以下是正确的 vue.config.js 配置&#xff1a; // vue.config.jsmodule.exports {devServ…...

大语言模型(LLM)与智能机器人的应用分析

系列文章目录 前言 近年来,大型语言模型(LLM)的集成彻底改变了机器人领域,使机器人能够以人类熟练程度进行交流、理解和推理。本文探讨了 LLM 对机器人的多方面影响,并针对在不同领域利用这些模型的关键挑战和机遇进行了研究。通过将 LLM 应用程序分类并分析核心机器人元素…...

String【Redis对象篇】

&#x1f3c6; 作者简介&#xff1a;席万里 ⚡ 个人网站&#xff1a;https://dahua.bloggo.chat/ ✍️ 一名后端开发小趴菜&#xff0c;同时略懂Vue与React前端技术&#xff0c;也了解一点微信小程序开发。 &#x1f37b; 对计算机充满兴趣&#xff0c;愿意并且希望学习更多的技…...

Elasticsearch高性能实践

前言 本方案主要从运维层面分析es是实际生产使用过程中的参数优化&#xff0c;深入理解es各个名词及含义&#xff0c;深入分析es的使用过程中应注意的点&#xff0c;详细解释参数设置的原因以及目的&#xff0c;主要包括系统层面&#xff0c;参数层面。除此之外&#xff0c;优…...

Maven 安装配置(详细教程)

文章目录 一、Maven 简介二、下载 Maven三、配置 Maven3.1 配置环境变量3.2 Maven 配置3.3 IDEA 配置 四、结语 一、Maven 简介 Maven 是一个基于项目对象模型&#xff08;POM&#xff09;的项目管理和自动化构建工具。它主要服务于 Java 平台&#xff0c;但也支持其他编程语言…...

sql server 创建索引实验

创建一个非主键索引&#xff0c;大小30G&#xff0c;数据文件增加了30G&#xff0c;日志文件增长了50G,4分钟完成&#xff0c; &#xff08;日志文件增加设置为2048MB 或者 256MB 执行时间都是4分钟&#xff0c;没有多大的时间差异&#xff09; 实验环境&#xff1a; 主机cpu…...

解决Vue项目中npm install卡住问题的详细指南

解决Vue项目中npm install卡住问题的详细指南 引言 在开发Vue项目时&#xff0c;我们经常会遇到npm install命令卡住的问题&#xff0c;特别是在构建依赖树时。本文将分享一些实用的解决方案&#xff0c;帮助您快速解决这一常见问题。 问题描述 在执行npm install时&#xf…...

手机实时提取SIM卡打电话的信令声音--社会价值(一、方案解决了什么问题)

手机实时提取SIM卡打电话的信令声音 --社会价值(一、方案解决了什么问题) 一、前言 这段时间&#xff0c;我们在技术范围之外陷入了一个自证或者说下定义的怪圈&#xff0c;即要怎么样去介绍或者描述&#xff1a;我们是一个什么样的产品。它在当前这个世界上&#xff0c;处于…...

35.1 thanos项目介绍和二进制部署

本节重点介绍 : 核心优点 无需维护存储&#xff0c;存储高可用&#xff1a; 利用廉价的公有云对象存储&#xff0c;高可用长时间存储&#xff0c;数据降采样&#xff1a;利用Compactor降采样完全适配原生prometheus查询接口&#xff1a;Query实现多级数据缓存配置 二进制部署 …...

【中工开发者】鸿蒙商城实战项目(启动页和引导页)

创建一个空项目 先创建一个新的项目选择第一个&#xff0c;然后点击finish 接下来为项目写一个名字&#xff0c;然后点击finish。 把index页面的代码改成下面代码块的代码&#xff0c;就能产生下面的效果 Entry Component struct Index {build() {Column(){Blank()Column(){…...

云计算IaaS-PaaS-SaaS三种服务模式转至元数据结尾

在当今数字化时代&#xff0c;云计算已经成为推动企业创新与发展的核心力量。而云计算的模型主要有三种&#xff1a;IAAS、PAAS 和 SAAS&#xff0c;它们各自在云计算的庞大体系中扮演着独特且关键的角色&#xff0c;恰似一座大厦的不同楼层&#xff0c;共同构建起强大而灵活的…...

Python爬虫:如何优雅地“偷窥”商品详情

在这个信息爆炸的时代&#xff0c;获取商品详情已经不再是简单的点击和浏览。我们需要的是速度、效率&#xff0c;还有一点点的...偷偷摸摸。没错&#xff0c;今天我们要聊的是如何使用Python爬虫来“偷窥”商品详情。别担心&#xff0c;我们保证一切都是合法合规的&#xff0c…...

自动化测试报错:Exception managing chrome: error decoding response body

报错&#xff1a;Exception managing chrome: error decoding response body 报错解释&#xff1a; 这个错误通常发生在使用Selenium WebDriver时&#xff0c;尝试管理&#xff08;例如关闭&#xff09;Chrome浏览器时出现了问题。具体来说&#xff0c;是在解码Chrome浏览器响…...

Dataset 与 JavaRDD

是的&#xff0c;Dataset 底层确实是基于 RDD 实现的&#xff0c;但它是通过更高层次的抽象和优化来提供更强大和易用的功能。以下是关于 Dataset 底层实现的一些详细信息&#xff1a; 1. RDD 是基础 RDD&#xff08;弹性分布式数据集&#xff09; 是 Spark 最基础的抽象&…...

【后端面试总结】Golang defer的实现原理和常见面试问题

前言 在Go语言中&#xff0c;defer关键字用于延迟函数的执行&#xff0c;即在包含defer语句的函数返回之前执行。这一特性使得defer在资源释放、文件关闭、解锁资源等场景中非常有用。本文将深入探讨defer的实现原理&#xff0c;并总结一些常见的面试问题。 基本使用 defer通…...

http 502 和 504 的区别

首先看一下概念&#xff1a; 502&#xff1a;作为网关或者代理工作的服务器尝试执行请求时&#xff0c;从上游服务器接收到无效的响应。503&#xff1a;由于临时的服务器维护或者过载&#xff0c;服务器当前无法处理请求。这个状况是临时的&#xff0c;并且将在一段时间以后恢…...

农业园区气象站

农业园区气象站是一种专为农业生产和科研设计的气象监测设备&#xff0c;它集成了多种传感器和技术&#xff0c;用于实时、准确地监测和记录农业园区内的气象数据。以下是农业园区气象站的主要功能和用处&#xff1a; 一、主要功能 实时监测&#xff1a;农业园区气象站能够实时…...

机器学习学习笔记-20241211

文章目录 空间归纳偏置局部性&#xff08;Locality&#xff09;平移不变性&#xff08;Translation Invariance&#xff09;空间关系&#xff08;Spatial Relationships&#xff09;尺度不变性&#xff08;Scale Invariance&#xff09;上下文依赖&#xff08;Context Dependen…...

【在Linux世界中追寻伟大的One Piece】HTTP Session

目录 1 -> 引入HTTP Session 1.1 -> 定义 1.2 -> 工作原理 1.3 -> 安全性 1.4 -> 超时和失效 1.5 -> 用途 2 -> 模拟session行为 3 -> 实验测试session 1 -> 引入HTTP Session 1.1 -> 定义 HTTP Session是服务器用来跟踪用户与服务器交…...

人工智能|自然语言处理——机器翻译评价指标Bleu和Rouge

在机器翻译任务中&#xff0c;BLEU 和 ROUGE 是两个常用的评价指标&#xff0c;BLEU 根据精确率(Precision)衡量翻译的质量&#xff0c;而 ROUGE 根据召回率(Recall)衡量翻译的质量 BLEU&#xff08;Bilingual Evaluation Understudy&#xff09;&#xff1a; BLEU是一种用于评…...

【前端】JavaScript中的函数形式参数:预解析与作用域详解

博客主页&#xff1a; [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: 前端 文章目录 &#x1f4af;前言&#x1f4af;示例代码&#x1f4af;1. 形式参数的预解析模拟预解析后的代码 &#x1f4af;2. 函数作用域与子函数的关系代码详解 &#x1f4af;3. 扩展&#xff1a;块作用域与变量提…...

自然语言处理的未来愿景

自然语言处理的未来愿景 在这个信息爆炸的时代,计算机如何理解和生成我们日常使用的语言,已经成为一个引人注目的问题。你有没有想过,为什么智能助手能理解你的指令?又或者,为什么社交媒体上的推荐引擎能够精准地推荐你喜爱的内容?这背后,正是自然语言处理(NLP)在发挥…...

Vmodel环境配置

1.conda create -n pytorch311 python3.11 # 重新进入虚拟环境 source activate # 退出虚拟环境 conda deactivate 最后&#xff0c;重新执行 conda activate pytorch311 pip install torch-2.0.0cpu-cp311-cp311-linux_x86_64 配置Graph-WaveNet网络&#xff1a; pip…...

nvm-windows | node版本管理

问题&#xff1a; npm ERR! notsup Not compatible with your version of node/npm: npm10.9.2 npm ERR! notsup Required: {"node":"^18.17.0 || >20.5.0"} npm ERR! notsup Actual: {"npm":"9.5.0","node":"v18.…...

GLM-4V-Flash:智谱AI引领多模态视觉模型新潮流

点击访问 chatTools 免费体验GPT最新模型&#xff0c;包括o1推理模型、GPT4o 和Claude等模型&#xff01; 随着人工智能技术的不断进步&#xff0c;多模态模型逐渐成为行业关注的焦点。智谱AI作为国内领先的人工智能公司&#xff0c;再次以创新姿态推出了首款免费多模态视觉模型…...

二、ubuntu单盘改软raid1

将单盘系统转换为软 RAID 1 是一个复杂的过程&#xff0c;尤其是在已经有数据的生产环境中进行时。这个过程涉及备份现有数据、创建 RAID 阵列、迁移数据以及更新引导加载程序&#xff08;如 GRUB&#xff09;。以下是详细的步骤指南&#xff1a; 前提条件 备份数据&#xff…...

「Mac玩转仓颉内测版45」小学奥数篇8 - 排列组合计算

本篇将通过 Python 和 Cangjie 双语讲解如何计算排列与组合。这道题目旨在让学生学会使用排列组合公式解决实际问题&#xff0c;并加深对数学知识和编程逻辑的理解。 关键词 小学奥数Python Cangjie排列与组合 一、题目描述 编写一个程序&#xff0c;计算从 n 个不同元素中取…...

【零成本抽象】基本概念与在C++中的实现

零成本抽象概念是由 Bjarne Stroustrup 提出的,他在 1994 年的著作中就有相关设想,2016 年其在 C++ 大会登台演讲时,明确阐述了 C++ 中的 “零成本抽象” 这一理念。 一、零成本抽象概念 Bjarne Stroustrup提出的零成本抽象概念,是指在编程中使用高级抽象机制时,不会产生…...

域渗透入门靶机之HTB-Cicada

easy难度的windows靶机 信息收集 端口探测 nmap -sT --min-rate 10000 -p- 10.10.11.35 -oA ./port 发现开放了53&#xff0c;88&#xff0c;389等端口&#xff0c;推测为域控 进一步信息收集&#xff0c;对爆破的端口进行更加详细的扫描 小tips&#xff1a;对于众多的端口&…...

(仓颉) Cangjie 刷力扣基础语法小结

文章目录 &#x1f9d3;官方资料&#x1f9d3;力扣经典前 3 题&#x1f577;️[1. 两数之和 - 力扣&#xff08;LeetCode&#xff09;](https://leetcode.cn/problems/two-sum/description/)&#x1f577;️[2. 两数相加 - 力扣&#xff08;LeetCode&#xff09;](https://leet…...