哈夫曼树Huffman

哈夫曼树处理这样的一种问题：

给出一棵n个叶子的k叉树，每个叶子有一个权值wi，要求最小化∑wi*di

di表示，第i个叶子节点到根节点的距离。（一般是边数）

处理方法比较固定。

贪心的思路：我们让权值较大的叶子节点的深度越小越好。

建立一个小根堆。

1.插入n个叶子的权值。

2.每次取出最小的k个，ans+=这些权值和。

3.合并出一个父亲节点，权值就是这k个点的权值和。（通常这一步不用真正实现，只是助于理解）

4.把这个新的父亲节点权值放进小根堆里面。

5.重复2~4操作，直到堆中只有一个节点（就是根节点）

但是这样是有问题的。

发现，我们每取出一次，合并一次，就是相当于把取出来的这些叶子深度+1，

最后一次合并的所有节点，就是根节点的儿子，他们的深度最浅。就是1

而可能出现，最后一次，堆中有2~k-1个节点，不能使最浅的一层放满。

这样肯定是不优的，因为我们可以把较深的一个节点放在根节点的儿子位置上。（因为这一层还没有放满）使得答案更优。

我们这样处理这个问题：

往堆里面不断加入权值为0的及节点。直到满足(tot-1)%(k-1)==0 tot是初始堆中节点个数。

这样，每次都可以恰好取出k个，并且0值的点会先取出来，相当于这里是空位，他们不会影响最后的值。

并且，这样保证了最浅的一层尽可能的放满，就一定是最优解了。

相当于把空位留给了更深的位置。

例题:

1.合并果子

Description：

n堆果子，合并两堆果子，花费两堆果子的重量之和的力气。问合成一堆最少用多少力气？

Solution：

浅显的解释就是贪心了，因为要合并固定的n-1次，必然每次选择最小的两个合并。

本质上其实是一棵n节点的2叉哈夫曼树。叶子节点的深度米就是这个原始堆被合并的次数。

2.荷马史诗

Description：

荷马史诗

Solution：

我们利用tire树的结构来考虑，为了保证没有前缀包含关系，最后建出的trie必然是有n个叶子节点。

每个叶子节点到根节点的路径长度就是单词长度，并且这个长度要乘上出现的次数wi

恰好就是Huffman的模型！！

一切就很裸了。

但是还要求一个最长的单词最短，，

那么，就在权值相同的节点中，选择之前已经合并过的次数最小的点合并，也就是那些当前深度最浅的点。

这样，把深度“平均”了一下，就是最优的情况了。

另外，新合并出来的点的合并次数，即深度，就是最大的所选点的合并次数。

代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=+;

int n,k,tot;

ll w[N];

ll ans,mx;

struct node{

    ll val,mer;

    bool friend operator <(node a,node b){

        if(a.val==b.val) return a.mer>b.mer;

        return a.val>b.val;

    }

};

priority_queue<node>q;

int main()

{

    scanf("%d%d",&n,&k);

    for(int i=;i<=n;i++){

        scanf("%lld",&w[i]);

        node nn;nn.val=w[i],nn.mer=;

        q.push(nn);

    }

    tot=n;

    while((tot-)%(k-)){

        node nn;nn.val=;nn.mer=;

        q.push(nn);tot++;

    }

    while(q.size()>){

        ll sum=;

        ll big=;

        for(int i=;i<=k;i++){

            node bb=q.top();q.pop();

            sum+=bb.val;

            big=max(big,bb.mer);

        }

        mx=max(mx,big+);

        ans+=sum;

        node kk;kk.val=sum;kk.mer=big+;

        q.push(kk);

    }

    printf("%lld\n%lld",ans,mx);

    return ;

}

巴特西

哈夫曼树Huffman

最新文章

热门文章