问题

给出一些字符和这些字符的出现频率，对这些字符用二进制进行编码，使得任意一个编码不是另一个编码的前缀，且编码的加权长度和最小。

解析

显然对于出现频率高的字符用更短的二进制进行编码，对出现频率低的字符用更长的二进制进行编码会得到编码加权长度和最小的结果。
这个问题可以用哈夫曼编码树来解决。
哈夫曼编码
1.取出所有数字中出现频率最低的两个，作为二叉树上的两棵子树，两者频率之和作为这两颗子树的根
2.将根作为新的节点投入序列中
3.重复1，2操作直到序列中只剩一个点
4.以最后一个点为根，遍历整颗二叉树，以经过的路径作为字符的编码，向左子树移动记为1，向右子树移动记为0

设计

priority_queue<pii, vector<pii>, greater<pii>> q;
    for (int i = 1; i <= n; ++i)
    {
        read(t);
        q.push(pii(t, ++node));
        rid[i] = node;
    }
    while (q.size() > 1)
    {
        pii u = q.top();
        q.pop();
        pii v = q.top();
        q.pop();
        addedge(++node, u.second);
        addedge(node, v.second);
        q.push(pii(u.first + v.first, node));
    }
    int root = q.top().second;
    q.pop();
    encode(root, 0);


void encode(int u,int cnt)
{
    code[cnt] = 0;
    if(rid[u])
    {
        printf("Code of %d : %s\n", rid[u], code);
        return;
    }
    for (int i = head[u], c = 0; ~i; i = edge[i].next, c ^= 1)
    {
        int v = edge[i].to;
        code[cnt] = '0' + c;
        encode(v, cnt + 1);
    }
}

分析

设待编码的字符共有n个
考虑到每次操作会删除两个数，再新增一个数，也就是说每次会减少一个数，共n次
找到最小值的复杂度是 $O(n)$ ,故总复杂度为 $O(n^2)$
用优先队列优化，插入的复杂度为 $O(\log n)$ ,取出的复杂度为 $O(1)$ ,总复杂度为 $O(n\log n)$
每两个点会在二叉树上产生一个新的点，计 $n$ 个字符***生 $f(n)$ 个点 $\begin{align} f(n)&=n+f(\frac{n}{2})\\ f(\frac{n}{2})&=\frac{n}{2}+f(\frac{n}{4})\\ &……\\ f(1)&=1 \end{align}$

逐项相加后 $f(n)=n+\frac{n}{2}+\frac n4+……+1=\sum_{i=0}^{1+\log n}2^i=2n$
所以编码树上点不超过 $2n$ 个
遍历整颗二叉树，总复杂度 $O(n)$
总复杂度 $O(n^2)$
或 $O(n\log n)$ 小顶堆优先队列优化情况下

源码

传送门

算法课-哈夫曼编码

问题

解析

设计

分析

源码