Huffman 模板

Huffman問題

就很greedy的把最小的兩個相加丟進去，用heap優化--> O(n lg n)

範例問題：http://poj.org/problem?id=3253

//Huffman
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;

typedef long long LL;

const int MAX_N = 200001;
LL num[MAX_N];

int main () {
    int n;
    priority_queue<int, vector<int>, greater<int> > pq;
    while (scanf("%d",&n) != EOF) {
        for (int x=0;n>x;x++) {
            scanf("%d",&num[x]);
            pq.push(num[x]);
        }
        if (n==1) {
            printf("%d\n",num[0]);
            continue;
        }
        LL sum=0;
        while (pq.empty()==false) {
            int ta=pq.top();
            pq.pop();
            int tb=pq.top();
            pq.pop();
            int tmp=ta+tb;
            sum+=tmp;
            if (pq.empty()) break;
            pq.push(tmp);
        }
        printf("%lld\n",sum);
    }
}