数据结构:解读哈夫曼树

栏目: 数据库 · 发布时间: 5年前

内容简介:在一棵数中,从任意一个结点到达另一个结点的通路被称为路径,改路径上所需经过的边的个数被称为该路径的长度。给定n个结点和它们的权值,以它们为叶子结点构造一颗带权路径长度和最小的二叉树,该二叉树即为哈夫曼树,同时也被称为最优数。

数据结构:解读哈夫曼树

哈夫曼树简介

在一棵数中,从任意一个结点到达另一个结点的通路被称为路径,改路径上所需经过的边的个数被称为该路径的长度。

给定n个结点和它们的权值,以它们为叶子结点构造一颗带权路径长度和最小的二叉树,该二叉树即为哈夫曼树,同时也被称为最优数。

哈夫曼树的求法

  1. 将所有结点放入集合K。
  2. 若集合K中剩余结点大于2个,则取出其中权值最小的两个结点,构造它们同时为某个新结点的左右子结点,该新结点是他们共同的双亲结点,设定它的权值为其两个儿子结点的权值和。并将该父亲结点放入集合K.重复步骤2 、3。
  3. 若集合K中仅剩余一个结点,该结点即为构造出的哈夫曼树的根节点,所有构造得到的中间结点的权值和即为该哈夫曼树的带权路劲和。

为了方便快捷高效率的求得集合K中权值最小的两个元素,我们需要堆数据结构。它可以以O(logn)的复杂度取得n个元素中的最小元素。为了绕过对堆得实现,我们使用标准模板库中的相应的标准模板 —— 优先队列

priority_queue<int> Q

这样建立的堆其默认为大顶锥,而在哈夫曼树中,我们恰恰需要取得堆中最小的元素,预算我们使用如下语句定义一个小顶堆。

priority_queue<int, vector<int>,greater<int>> Q

代码块

priority_queue<int ,vector<int>,greater<int> > Q;    //建立一个小顶堆

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF){
        while(Q.empty()==false) Q.pop();        //清空堆中的元素
        for(int i=1;i<=n;i++){                  //输入n个叶子结点权值
            int x;
            scanf("%d",&x);                     //讲权值放入堆中
            Q.push(x);
        }
        int ans=0;
        while(Q.size()>1){
            int a=Q.top();
            Q.pop();
            int b=Q.top();
            Q.pop();
            ans+=a+b;
            Q.push(a+b);
        }
        printf("%d\n",ans);
    }
    return 0;
}

以上所述就是小编给大家介绍的《数据结构:解读哈夫曼树》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

第四次革命

第四次革命

[意]卢西亚诺•弗洛里迪(Luciano Floridi)著 / 王文革 / 浙江人民出版社 / 2016-5 / 64.90元

 随着线上线下大融合以及人工智能的极大发展,人类已经进入超历史时代。在这一时代中,人类终于迎来了继哥白尼革命、达尔文革命、神经科学革命之后自我认知的第四次革命——图灵革命,整个世界正化身为一个信息圈,每个人都生活在云端,人类已不再是信息圈毋庸置疑的主宰。毫无疑问,图灵革命引爆了人工智能重塑整个人类社会的序曲!  那么在人工智能时代,人类如何保证自己最钟爱的财富——“隐私”不被窃取?如何应......一起来看看 《第四次革命》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

UNIX 时间戳转换
UNIX 时间戳转换

UNIX 时间戳转换