哈夫曼树（详见CLRS）
这题设计的很巧妙
理解的关键是: 将切割木板的过程反过来观察，也就是将所有最终的短木板进行拼接的过程，这其实就是哈夫曼树的构造过程
CLRS上关于哈夫曼树的构造是以优先级队列为基础的
由于倾向于用C来写，所以并没有使用C++的STL（当然，这要简单的多）
别忘了: 目的并不是要简单，而是要锻炼自己的算法及数据结构基础
以最小堆为基础的优先级队列实现:
1 #define PARENT(i) ((i-1)>>1)
2 #define LEFT_CLD(i) ((i<<1)+1)
3 #define RIGHT_CLD(i) ((i+1)<<1)
4 #define SWAP(a, b) a=a+b; b=a-b; a=a-b /* tricky */
5 int heap_size;
6
7 void
8 min_heapify(long long *heap, int i)
9 {
10 int min = i;
11 int left = LEFT_CLD(i);
12 int right = RIGHT_CLD(i);
13 if(left<heap_size && heap[min]>heap[left])
14 min = left;
15 if(right<heap_size && heap[min]>heap[right])
16 min = right;
17 if(min != i) {
18 SWAP(heap[i], heap[min]);
19 min_heapify(heap, min);
20 }
21 }
22
23 void
24 build_min_heap(long long *heap, int length)
25 {
26 int i;
27 heap_size = length;
28 for(i=(heap_size>>1)-1; i>=0; i--)
29 min_heapify(heap, i);
30 }
31
32 long long
33 extract_min(long long *heap)
34 {
35 if(heap_size < 1) {
36 fprintf(stderr, "heap underflow\n");
37 exit(1);
38 }
39 long long rt = heap[0];
40 SWAP(heap[0], heap[heap_size-1]);
41 --heap_size;
42 min_heapify(heap, 0);
43 return rt;
44 }
45
46 void
47 decrease_key(long long *heap, int i, long long new_key)
48 {
49 int c, p;
50 if(heap[i] < new_key) {
51 fprintf(stderr, "new key is larger than current key\n");
52 exit(1);
53 }
54 heap[i] = new_key;
55 c = i;
56 p = PARENT(i);
57 while(c>0 && heap[p]>heap[c]) {
58 SWAP(heap[c], heap[p]);
59 c = p;
60 p = PARENT(c);
61 }
62 }
63
64 void
65 insert(long long *heap, long long value)
66 {
67 ++heap_size;
68 heap[heap_size-1] = MAX_INT;
69 decrease_key(heap, heap_size-1, value);
70 }
哈夫曼树的构造(这里是简化版，根据题意只需要计算cost即可):
1 long long
2 huffman_tree_way(long long *heap, int length)
3 {
4 int i;
5 long long fst, snd, sum, rt=0;
6 build_min_heap(heap, length);
7 for(i=0; i<length-1; i++) {
8 fst = extract_min(heap);
9 snd = extract_min(heap);
10 sum = fst + snd;
11 rt += sum;
12 insert(heap, sum);
13 }
14 return rt;
15 }