【堆 && 哈弗曼树】树-堆结构练习——合并果子之哈夫曼树

堆排序的应用之哈夫曼树

1952年, David A. Huffman提出了一个不同的算法，这个算法可以为任何的可能性提供出一个理想的树。香农-范诺编码（Shanno-Fano）是从树的根节点到叶子节点所进行的的编码，哈夫曼编码算法却是从相反的方向，暨从叶子节点到根节点的方向编码的。

1、为每个符号建立一个叶子节点，并加上其相应的发生频率
2、当有一个以上的节点存在时，进行下列循环:

1. 把这些节点作为带权值的二叉树的根节点，左右子树为空
2. 选择两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且至新的二叉树的根结点的权值为其左右子树上根结点的权值之和。
3. 把权值最小的两个根节点移除
4. 将新的二叉树加入队列中。

5、最后剩下的节点暨为根节点，此时二叉树已经完成。

这里附上一个水题：树-堆结构练习——合并果子之哈夫曼树

有两种做法一种使用堆，一种是快排。运行时间差的很多。用堆排序的做法运行时间只有4ms，而快排是112ms。所以建议用哈夫曼数写。也就是第一个代码。

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 10005
long long int a[N];
int size;

void Insert(long long int m)
{
    a[++size] = m;
    int i;
    for(i = size; i != 0; i /= 2)
    {
        if(a[i] < a[i/2])
        {
            long long int t = a[i];
            a[i] = a[i/2];
            a[i/2] = t;
        }
        else
            break;
    }
}

void Delete()
{
    a[1] = a[size--];
    int i, x;
    for(i = 1; 2 * i <= size; i = x)
    {
        if(2 * i + 1 <= size && a[i * 2] > a[i * 2 + 1])
            x = i * 2 + 1;
        else
            x = i * 2;
        if(a[i] > a[x])
        {
            long long int t = a[i];
            a[i] = a[x];
            a[x] = t;
        }
        else
            break;
    }
}

int main()
{
    int n, i;
    scanf("%d", &n);
    for(i = 0; i < n; i++)
    {
        long long int m;
        scanf("%lld", &m);
        Insert(m);
    }
    long long int sum, ans = 0;
    while(size > 1)
    {
        int x = a[1];
        Delete();
        int y = a[1];
        Delete();
        sum = x + y;
        ans += sum;
        Insert(sum);
    }
    printf("%lld
", ans);
    return 0;
}

另一种用快排的做法也附上：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 100005
int a[100005];
void Qsort(int left, int right)
{
    int x = a[left];
    int i = left, j = right;
    if(i >= j) return;
    while(i < j)
    {
        while(i < j && a[j] >= x) j--;
        a[i] = a[j];
        while(i < j && a[i] <= x) i++;
        a[j] = a[i];
    }
    a[i] = x;
    Qsort(left, i - 1);
    Qsort(i + 1, right);
}

int main()
{

    int n, i, j;
    scanf("%d", &n);
    for(i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    Qsort(1, n);
    long long int sum = 0, ans = 0;
    for(i = 1; i < n; i++)
    {
        sum = a[i] + a[i + 1];
        ans += sum;
        for(j = i + 2; j <= n;j++)
        {
            if(sum > a[j])
                a[j - 1] = a[j];
            else
            {
                break;
            }
        }
        a[j - 1] = sum;
    }
    printf("%lld
", ans);
    return 0;
}