哈夫曼樹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.荷馬史詩

荷馬史詩

我們利用tire樹的結構來考慮，為了保證沒有字首包含關系，最後建出的trie必然是有n個葉子節點。

每個葉子節點到根節點的路徑長度就是單詞長度，并且這個長度要乘上出現的次數wi

恰好就是Huffman的模型！！

一切就很裸了。

但是還要求一個最長的單詞最短，，

那麼，就在權值相同的節點中，選擇之前已經合并過的次數最小的點合并，也就是那些目前深度最淺的點。

這樣，把深度“平均”了一下，就是最優的情況了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100000+10;
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=1;i<=n;i++){
        scanf("%lld",&w[i]);
        node nn;nn.val=w[i],nn.mer=0;
        q.push(nn);
    }
    tot=n;
    while((tot-1)%(k-1)){
        node nn;nn.val=0;nn.mer=0;
        q.push(nn);tot++;
    }
    while(q.size()>1){
        ll sum=0;
        ll big=0;
        for(int i=1;i<=k;i++){
            node bb=q.top();q.pop();
            sum+=bb.val;
            big=max(big,bb.mer);
        }
        mx=max(mx,big+1);
        ans+=sum;
        node kk;kk.val=sum;kk.mer=big+1;
        q.push(kk);
    }
    printf("%lld\n%lld",ans,mx);
    return 0;
}