备战快速复习--day9

哈夫曼树和哈夫曼编码相关。

哈夫曼树主要解决的问题：有n个堆，将他们合成成一个堆的过程中怎么能消耗最少。（每次选中两个合并，当次消耗为两个的体力之和）

每次选中两个最小的堆就行，合并完以后用和作为新的节点加入。

可以使用优先队列实现。（优先队列默认是降序的，用greater改成升序）

#include<queue>
#include<iostream>
#include<stdio.h>
#include<vector>
using namespace std;
int main()
{
    priority_queue<int,vector<int>,greater<int> >q;
    int n;
    scanf("%d",&n);
    int temp,ans=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&temp);
        q.push(temp);
    }
    int temp1,temp2;
    while(q.size()>1)
    {
        temp1=q.top();
        q.pop();
        temp2=q.top();
        q.pop();
        ans+=temp1+temp2;
        q.push(temp1+temp2);
    }
    printf("%d ",q.top());
    printf("%d",ans);
    return 0;
}

哈弗曼编码，保证编码过程中各个点不能成为其他节点的前缀导致解释错误。

所有的点都在叶子节点当中。这样保证了他们的前缀是不一样的。左0右1。

关于带权的解释：分为点权和边权。在哈弗曼树上面的应用场景中。点权*自己边权（默认的1，n条为n）是这个堆的消耗

而在编码的过程中，点权是点在里面出现的次数，每个边是1，这样算出来的是总共的字符串长度。

为了减少总的长度，也是根据出现频率为消耗用哈弗曼树完成，所有点都在叶子。

实际接替过程中用优先队列可以方便的计算出消耗。求具体编码需要实现树。（暂时超纲）