哈夫曼树¶

哈夫曼树（Huffman Tree），也被称为霍夫曼树或最优二叉树，是一种带权路径长度最短的二叉树，常用于数据压缩。它由美国数学家大卫·哈夫曼提出。

哈夫曼树的核心思想是以叶子节点的权值（通常是字符出现的频率）作为构建树的依据，频率高的字符拥有更短的编码路径，频率低的字符则路径较长。以下是哈夫曼树的基本特点和构建步骤：

特点¶

权值：树中的每个叶子节点都带有一个权值，权值通常代表某个字符出现的频率。
路径：从根节点到叶子节点的路径长度与该叶子节点的权值有关，权值越大的叶子节点离根节点越近。
最优性：在所有包含相同权值节点的二叉树中，哈夫曼树的带权路径长度是最短的。

构建步骤¶

排序：将所有节点按照权值（频率）从小到大排序。
选取：每次从排序好的节点中取出两个权值最小的节点，创建一个新的内部节点作为它们的父节点，这个新节点的权值是这两个子节点权值的和。
替换：将这两个最小的节点从列表中移除，并将新创建的父节点添加到列表中。
重复：重复步骤2和3，直到列表中只剩下一个节点，这个节点就是哈夫曼树的根节点。

应用¶

哈夫曼树的主要应用是在数据压缩领域，通过它构建的哈夫曼编码可以实现无前缀编码，即没有任何一个编码是另一个编码的前缀，这样就可以保证编码的唯一可解性。（见例题 #1）

哈夫曼编码的过程就是根据哈夫曼树从根节点到叶子节点的路径来为每个字符指定一个唯一的二进制编码，路径上的左分支代表0，右分支代表1。

由于哈夫曼树和编码对于不同数据的统计特性非常敏感，因此它们在文件压缩，尤其是文本文件的压缩中非常有效。

例题 #1 [NOI2015] 荷马史诗¶

题目描述

Allison 最近迷上了文学。她喜欢在一个慵懒的午后，细细地品上一杯卡布奇诺，静静地阅读她爱不释手的《荷马史诗》。但是由《奥德赛》和《伊利亚特》组成的鸿篇巨制《荷马史诗》实在是太长了，Allison 想通过一种编码方式使得它变得短一些。

一部《荷马史诗》中有 \(n\) 种不同的单词，从 \(1\) 到 \(n\) 进行编号。其中第 \(i\) 种单词出现的总次数为 \(w_i\)。Allison 想要用 \(k\) 进制串 \(s_i\) 来替换第 \(i\) 种单词，使得其满足如下要求：

对于任意的 \(1\leq i, j\leq n\) ，\(i\ne j\) ，都有：\(s_i\) 不是 \(s_j\) 的前缀。

现在 Allison 想要知道，如何选择 \(s_i\)，才能使替换以后得到的新的《荷马史诗》长度最小。在确保总长度最小的情况下，Allison 还想知道最长的 \(s_i\) 的最短长度是多少？

一个字符串被称为 \(k\) 进制字符串，当且仅当它的每个字符是 \(0\) 到 \(k-1\) 之间（包括 \(0\) 和 \(k-1\) ）的整数。

字符串 \(str1\) 被称为字符串 \(str2\) 的前缀，当且仅当：存在 \(1 \leq t\leq m\) ，使得 \(str1 = str2[1..t]\)。其中，\(m\) 是字符串 \(str2\) 的长度，\(str2[1..t]\) 表示 \(str2\) 的前 \(t\) 个字符组成的字符串。

输入格式

输入的第 \(1\) 行包含 \(2\) 个正整数 \(n, k\) ，中间用单个空格隔开，表示共有 \(n\) 种单词，需要使用 \(k\) 进制字符串进行替换。

接下来 \(n\) 行，第 \(i + 1\) 行包含 \(1\) 个非负整数 \(w_i\)，表示第 \(i\) 种单词的出现次数。

输出格式

输出包括 \(2\) 行。

第 \(1\) 行输出 \(1\) 个整数，为《荷马史诗》经过重新编码以后的最短长度。

第 \(2\) 行输出 \(1\) 个整数，为保证最短总长度的情况下，最长字符串 \(s_i\) 的最短长度。

所有测试数据的范围和特点如下表所示（所有数据均满足 \(0 < w_i \leq 10^{11}\)）：

测试点编号	\(n\) 的规模	\(k\) 的规模
for all	n≤100,000	k≤9

构建K叉哈夫曼树。

/*                                                                                
                      Keyblinds Guide
                    ###################
      @Ntsc 2024

      - Ctrl+Alt+G then P : Enter luogu problem details
      - Ctrl+Alt+B : Run all cases in CPH
      - ctrl+D : choose this and dump to the next
      - ctrl+Shift+L : choose all like this
      - ctrl+K then ctrl+W: close all
      - Alt+la/ra : move mouse to pre/nxt pos'

*/
#include <bits/stdc++.h>
#include <queue>
using namespace std;

#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define pii pair<int, int>
#define ps second
#define pf first

// #define innt int
#define itn int
// #define inr intw
// #define mian main
// #define iont int

#define rd read()
int read(){
    int xx = 0, ff = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            ff = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
      xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
void write(int out) {
    if (out < 0)
        putchar('-'), out = -out;
    if (out > 9)
        write(out / 10);
    putchar(out % 10 + '0');
}

#define ell dbg('\n')
const char el='\n';
const bool enable_dbg = 1;
template <typename T,typename... Args>
void dbg(T s,Args... args) {
    if constexpr (enable_dbg){
    cerr << s;
    if(1)cerr<<' ';
        if constexpr (sizeof...(Args))
            dbg(args...);
    }
}

#define zerol = 1
#ifdef zerol
#define cdbg(x...) do { cerr << #x << " -> "; err(x); } while (0)
void err() { cerr << endl; }
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x) { for (auto v: a) cerr << v << ' '; err(x...); }
template<typename T, typename... A>
void err(T a, A... x) { cerr << a << ' '; err(x...); }
#else
#define dbg(...)
#endif


const int N = 3e5 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;

struct node{
    int w,h;
    bool operator <(const node b)const{
        if(w==b.w)return h>b.h;
        return w>b.w;
    }
};

priority_queue<node> pq;

void solve(){
    int n=rd,K=rd;

    int ans=0;

    for(int i=1;i<=n;i++){
        int w=rd;
        pq.push({w,1});
    }

    while((pq.size()-1)%(K-1)!=0)pq.push({0,1});//补全树

    while(pq.size()>=K){
        int h=-1,w=0;
        for(int i=1;i<=K;i++){
            node t=pq.top();
            pq.pop();
            h=max(h,t.h);
            w+=t.w;
        }

        ans+=w;
        pq.push({w,h+1});
    }

    cout<<ans<<endl;
    cout<<pq.top().h-1<<endl;
}

signed main() {
    // freopen(".in","r",stdin);
    // freopen(".in","w",stdout);

    int T=1;
    while(T--){
        solve();
    }
    return 0;
}

哈夫曼编码¶

哈夫曼编码并不是说出现频率最大的字符的编码就是1个bit或者几个bit。很多同学会问为什么有些时候频率最大的字符的编码长度是1，有些时候是2，那么到底是几？其实完全不是这样。

前缀编码：要设计长度不等的编码，则必须使任一字符的编码都不是另一个字符的编码的前缀

哈夫曼编码的要求就是它必须符合**前缀编码**的条件。那么我们怎么样来对给定的字符集和概率求出其哈夫曼编码呢？我们可以模拟一下流程：

我们将字符作为节点，并且将概率视为权值。那么我们需要先构建一颗哈夫曼树。

初始化：由给定的n个权值构造m棵只有一个根节点的二叉树，得到一个二叉树集合F。
选取与合并：从二叉树集合\(F\) 中选取根节点权值最小的两棵二叉树分别作为左右子树（通常让更小的在左）构造一棵新的二叉树，这颗新二叉树的根节点的权值为其左、右子树根结点的权值和。
重复2，当集合中只剩下一棵二叉树时，这棵二叉树就是霍夫曼树。

构建完哈夫曼树后，我们将每个节点的左儿子边设为0，右儿子边设为1，然后一个字符的编码就是根节点到它路径上的01串了。