STEP5 0031 : 蘿莉切割問題

[霍夫曼HEAP]
兩個兩個一串==>霍夫曼編碼

O(NlgN)

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<cstring>
#define INF 0
#define LL  unsigned long long int
#define N 200000
class minHeap
{
private:
    LL a[N];
    int cnt;
public:
    minHeap()
    {
        memset(a,(LL)INF,sizeof(a));
        cnt=0;
    }
    void add(LL inp)
    {
        a[++cnt]=inp;
        for(int prc=cnt;prc/2;prc/=2)
            if(a[prc]<a[prc/2])
                a[prc]^=a[prc/2]^=a[prc]^=a[prc/2];
            else
                break;
    }
    LL getmin()
    {
        if(cnt==0) return -1;
        return a[1];
    }
    void remove()
    {
        a[1]=a[cnt];
        a[cnt]=INF;
        cnt--;
        int prc=1;
        while(1)
        {
            if(prc*2>cnt) break;
            if(a[prc*2]==INF) break;
            if(a[prc*2+1]==INF)
            {
                if(a[prc]>a[prc*2])
                    a[prc*2]^=a[prc]^=a[prc*2]^=a[prc];
                prc*=2;
                continue;
            }
            if((a[prc]<=a[prc*2])&&(a[prc]<=a[prc*2+1])) break;
            else if(a[prc*2]>=a[prc*2+1])
            {
                a[prc*2+1]^=a[prc]^=a[prc*2+1]^=a[prc];
                prc=prc*2+1;
            }
            else
            {
                a[prc*2]^=a[prc]^=a[prc*2]^=a[prc];
                prc*=2;
            }
        }
    }
};
int main()
{
    minHeap mh;
    int n;      scanf("%d",&n);
    LL cost=0;
    LL inp;
    for(int lx=0;lx<n;lx++)
    {
        scanf("%I64u",&inp);
        mh.add(inp);
    }
    LL a,b;
    for(int lx=1;lx<=n-1;lx++)
    {
        a=mh.getmin();
        mh.remove();
        b=mh.getmin();
        mh.remove();
        cost+=a+b;
        mh.add(a+b);
    }
    printf("%I64u\n",cost);
    return 0;
}