5-12 修理牧场 (25分)——最小堆->哈夫曼树+快速排序

    测试点1    答案正确    12/12   1   1   sample
    测试点2    答案正确    1/1     2   1   只有一段木头，不用锯
    测试点3    答案正确    6/6     5   1   最大N，最长木段，输出的最大值
    测试点4    答案正确    6/6     6   1   最大N随机数据

    #include <stdio.h>
    #include <stdlib.h>
    #define MINDATA -1
    typedef struct node
    {
    int *Data;
    int Size;
    }MinHeap;
    MinHeap * Creat(int MaxSize)
    {
    MinHeap *H = (MinHeap *)malloc(sizeof(MinHeap));
    H->Data = (int *)malloc((MaxSize + 1)*sizeof(int));
    H->Size = 0;
    H->Data[0] = MINDATA;
    return H;
    }
    void Insert(MinHeap *H, int x)
    {
    int i = ++H->Size;
    for(; H->Data[i/2] >= x; i /= 2)
        H->Data[i] = H->Data[i/2];
    H->Data[i] = x;
    }
    int Delete(MinHeap *H)
    {
    int MinItem, X, parent, child;
    MinItem = H->Data[1];
    X = H->Data[H->Size--];
    for(parent = 1; parent*2 <= H->Size; parent = child)
    {
        child = parent*2;
        if((child != H->Size) && H->Data[child] > H->Data[child+1])
            child++;
        if(X <= H->Data[child])
            break;
        else
            H->Data[parent] = H->Data[child];
    }
    H->Data[parent] = X;
    return MinItem;
    }
    void PercDown(MinHeap *H, int p)
    {
    int X, parent, child;
    X = H->Data[p];
    for(parent = p; parent*2 <= H->Size; parent = child)
    {
        child = parent*2;
        if((child != H->Size) && H->Data[child] > H->Data[child+1])
            child++;
        if(X <= H->Data[child])
            break;
    }
    H->Data[parent] = X;
    }
    void GetBuild(MinHeap *H)
    {
    for(int i = H->Size/2; i > 0; i--)
    {
        PercDown(H, i);
    }
    }
    int cmp(const void *a, const void *b)
    {
    return ((*(int *)a) - (*(int *)b));
    }
    int main()
    {
    int n, i, x1, x2, sum, y, ans[14000];
    MinHeap *H1;
    while(scanf("%d", &n) != EOF)
    {
        sum = 0;
        H1 = Creat(n);
        H1->Size = n;
        for(i = 1; i <= n; i++)
        {
            scanf("%d", &ans[i]);
        }
        qsort(&ans[1], n, sizeof(ans[1]), cmp);
        for(i = 1; i <= n; i++)
        {
            H1->Data[i] = ans[i];
        }
        GetBuild(H1);
        for(i = 0; i < n-1; i++)
        {
            x1 = Delete(H1);
            x2 = Delete(H1);
            y = x1 + x2;
            sum += y;
            Insert(H1, y);
        }
        printf("%d\n", sum);
    }
    }