图解哈夫曼树

简介: 图解哈夫曼树

前言:

哈夫曼树实际是一种编码方式,主要用在压缩数据,其本质是求解带权路径的最小值的编排方式。

哈夫曼树:

1、定义:是一种特殊的二叉树,被称为“最优二叉树”。即带权路径长度最短。带权路径可以理解为到这些叶子结点的耗费之和

2、:赋予某个实体的一个量,也就是这个结点出现的频率

3、结点的带权路径长度:从该结点到树根之间的路径长度与结点上权的乘积

4、树的带权路径长度:树中所有叶子结点的带权路径长度之和,就是走完这些结点所需要的总耗费

图解如下:

5、带权路径长度:也等于所有根节点之和, 如上图19=3+6+10。这个证明过程这里就不具体展开了。简单来说就是这个3本身是a、b走一个路径所耗费的,6和10内除了包含新增的c、d路径耗费以外,也有a,b的3,即ab的3加了三次也就是ab的路径长度3乘上其权重都考虑了。

哈夫曼树的应用:

哈夫曼树最见的应用就是哈夫曼编码。一般的字母二进制编码的位数是一样的,我们想要让总体编码少的话就要减少每个字母的编码位数,但是如果都相同减少的话,会发生问题。例如3位二进制就无法表示15。而哈夫曼编码就是给不同频率出现的字母不同的长度的编码,在保证不会冲突的情况下,越常出现的字母给它越短的编码,从而让整体运用中所需要的编码总数最少。这个思想实际上就和我们带权路径和最短是相同的。

所以如果我们构造出一个哈夫曼树,他的带权路径和是最短的,也就是说他总体的编码总数也是最少的。这里假如一个路径连线是一个编码,那么按照上面这个图来说,ab离根节点的路径最长所以编码也最长,同时ab出现的频率即权重又是最小的,这就符合我们上一段说的,出现频率越少给他的编码越长的原则了。

下面我们再给这段分析一个图示:

到这里问题就转变为构造哈夫曼树了 !

构造哈夫曼树:

步骤:

1、选取所有结点中权值最小的两个,将其合并为树,并将根节点变为其权值之和。并且在所有节点中删除这两个结点

2、将上一步新生成的树看作一个新的结点,其权值就是之前两个结点的和。并将这个新结点放到所有结点的集合中

3、重复第一步第二步操作,直到只剩下一个新结点(即一个新树)。

见图示:

方法证明: (下面两个方法都可以证明)

1、反证法:假设找两个最小结点合并得到的带权路径和并不是最小的,即存在其他合并方法更小。假设B不与D合并而是和另外一个X合并,那么

“合并后的树到根节点的权重和减去原本的合并树到根节点的权重和”=“X到根节点的权重和减去之前D到根节点的和”。由于之前D和X到根节点路径长度相同,所以问题就变为两个权重谁大。权重越小则合并后的树到根节点的权重和越小,由于D最小所以 “合并后的树到根节点的权重和减去原本的合并树到根节点的权重和”为正数,即对任意X,合并后的树到根节点的权重和更大,故原假设不成立,不存在其他合并方法更小。

2、正面推理:读者自己证明

题目要求:

构造哈夫曼树,并求解哈夫曼树的最短路径之和。

题目分析:

构造哈夫曼树的难点在于每次都要找整个数组中最小的两个结点进行合并。所以我们要对整个数组进行排序,得到最小的结点,然后构造新的数组再排序。如果用一般的排序效率太低,所以一般采用堆排序,且是小根堆。(这里说一个点,实际上我们实现哈夫曼树也可以用其他的排序方式,只是对于树的问题用堆排序多好,树对树的逻辑结构实现多统一,嘻嘻,并且堆排序的各方面指标都很好)

而对于堆排序我们即可以采用priority_queue函数,也可以自己来实现这一个函数

代码展示:

一、利用stl函数

#include<bits/stdc++.h>
using namespace std;
const int N=1001;
int num[N];
int main(){
    int n=0;
    priority_queue<int,vector<int>,greater<int>> q;//小根堆
    cin>>n;
    for(int i=0;i<n;i++){
        int t=0;
        cin>>t;
        q.push(t);
    }
    int res=0;
    while(--n){
        int a1=q.top();q.pop();
        int a2=q.top();q.pop();
        res+=a1+a2;//每个根结点的值相加就是最终路径的总长度
        q.push(a1+a2);
    }
    cout<<res<<endl;
    return 0;
}

二、完全自己实现

#include <iostream>
using namespace std;
const int N = 1001;
int num[N];
template<class T>
class priority_greater_queue {
private:
    int size; // 用来存储队列的元素个数
    T heap[N]; // 用来存储队列的元素,用数组来存储
public:
    priority_greater_queue() {
        size = 0;
    }
    void up(int n) { // 把一个元素上浮到合理位置,n就是修改点目前的位置
        int t = n; // 修改的点目前所应该在的位置
        while (n / 2 > 0 && heap[n / 2] > heap[n]) {
            t = n / 2; // 改变修改点目前应该在的位置
            swap(heap[t], heap[n]); // 真正把点移动到t这个位置
            n = t; // 转移指针指向,进入下一轮上浮
        }
    }
    void down(int n) { // 把一个元素下沉到应该在的位置
        int t = n;
        if (n * 2 <= size && heap[n * 2] < heap[t]) t = n * 2;
        if (n * 2 + 1 <= size && heap[n * 2 + 1] < heap[t]) t = n * 2 + 1; // 在左右子树中找到应该在的位置
        if (n != t) {
            swap(heap[t], heap[n]);
            down(t);
        }
    }
    void push(int x) {
        heap[++size] = x;
        up(size);
    }
    int top() {
        return heap[1];
    }
    void pop() {
        heap[1] = heap[size];
        size--;
        down(1);
    }
};
int main() {
    int n = 0;
    priority_greater_queue<int> q;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int t = 0;
        cin >> t;
        q.push(t);
    }
    int res = 0;
    while (--n) {
        int a1 = q.top(); q.pop();
        int a2 = q.top(); q.pop();
        res += a1 + a2;
        q.push(a1 + a2);
    }
    cout << res << endl;
    return 0;
}
相关文章
|
7月前
|
人工智能 边缘计算 算法
AI人流热力图分析监测技术
通过深度学习算法(如CSRNet)进行实时密度估算和热力图生成,结合历史数据分析预测高峰时段,优化人员调度与促销活动。采用边缘计算减少延迟,确保实时响应,并通过数据可视化工具提升管理决策效率。
640 24
|
6月前
|
Java
ArrayList扩容机制
本文解析了Java中`ArrayList`的扩容机制。
212 70
|
10月前
|
存储 人工智能 算法
NFT元宇宙链游系统开发技术规则逻辑及源码示例
NFT元宇宙链游系统开发涉及区块链、NFT、智能合约等核心技术。区块链确保去中心化和透明性,NFT用于确认数字资产所有权,智能合约管理数字资产的交易。源码示例展示了基于Solidity的NFT链游智能合约,包括NFT的铸造、收获和查询功能。
|
10月前
|
移动开发 自然语言处理 JavaScript
虚拟 DOM 如何保证跨平台的兼容性?
【10月更文挑战第25天】虚拟 DOM 通过其抽象的表示、渲染器的解耦以及针对不同平台的特定渲染器实现、事件系统适配、样式处理兼容性和统一的数据绑定与状态管理等多方面的设计和机制,有效地保证了跨平台的兼容性,使得开发者能够使用一套代码在多种平台上构建具有一致体验和高性能的应用。
|
存储 缓存 监控
Web服务器
【7月更文挑战第19天】Web服务器
568 2
|
存储 Python
链表中删除节点
链表中删除节点
|
11月前
|
存储 物联网 计算机视觉
|
域名解析 网络协议 安全
【域名解析DNS专栏】DNS递归查询与迭代查询的区别及影响
【5月更文挑战第24天】DNS的递归查询与迭代查询是域名解析的两种方式。递归查询由客户端发起,DNS服务器负责全程解析,速度快但可能增加服务器负载和安全风险。迭代查询则需客户端参与多次查询,虽慢但分散负载,提高安全性。理解两者差异有助于优化网站访问体验和安全性。
2160 0
【域名解析DNS专栏】DNS递归查询与迭代查询的区别及影响
|
机器学习/深度学习 存储
数据结构学习记录——哈夫曼树(什么是哈夫曼树、哈夫曼树的定义、哈夫曼树的构造、哈夫曼树的特点、哈夫曼编码)
数据结构学习记录——哈夫曼树(什么是哈夫曼树、哈夫曼树的定义、哈夫曼树的构造、哈夫曼树的特点、哈夫曼编码)
450 1
|
编译器 C++
C++的基类和派生类构造函数
在 C++ 中,类的构造函数不能被继承,但基类的普通成员函数可以在派生类中访问。派生类必须通过其构造函数初始化继承的成员变量,由于私有成员变量无法直接初始化,因此需要在派生类构造函数中调用基类的构造函数来完成。示例代码显示了如何在派生类构造函数中调用基类构造函数,确保正确初始化。构造函数的调用顺序遵循自顶向下、从基类到派生类的规则,且只能调用直接基类的构造函数。如果基类没有默认构造函数,而派生类未指定构造函数调用,会导致编译错误。
231 4