哈夫曼樹（詳見CLRS）
這題設(shè)計的很巧妙
理解的關(guān)鍵是: 將切割木板的過程反過來觀察，也就是將所有最終的短木板進行拼接的過程，這其實就是哈夫曼樹的構(gòu)造過程
CLRS上關(guān)于哈夫曼樹的構(gòu)造是以優(yōu)先級隊列為基礎(chǔ)的
由于傾向于用C來寫，所以并沒有使用C++的STL（當然，這要簡單的多）
別忘了: 目的并不是要簡單，而是要鍛煉自己的算法及數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)
以最小堆為基礎(chǔ)的優(yōu)先級隊列實現(xiàn):
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 }
哈夫曼樹的構(gòu)造(這里是簡化版，根據(jù)題意只需要計算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 }