2010年02月13日星期六.sgu203 二叉堆
sgu203:堆,根據(jù)一個(gè)文章生成單詞出現(xiàn)次數(shù),求對(duì)這個(gè)文章進(jìn)行霍夫曼編碼之后的文章長度。
我郁悶，這個(gè)題想了半天，想了一個(gè)構(gòu)建二叉樹，然后記錄葉子節(jié)點(diǎn)深度,之后用最大深度減去這
個(gè)深度的方法。不過，我自己都覺得這個(gè)應(yīng)該過不了。。。
無意間看了一眼discuss，有一人的代碼寫了這么兩句
a = heap.pop(),b = heap.pop();
ans = ans + a + b;
一拍大腿，原來如此啊，我咋沒想到。。。
霍夫曼樹選擇兩個(gè)最小的加到新節(jié)點(diǎn)上，那么也就等于到這兩個(gè)小的節(jié)點(diǎn)的邊就被加到了新節(jié)點(diǎn)上。
也就是，隨著新節(jié)點(diǎn)的繼續(xù)累計(jì)，這個(gè)兩個(gè)節(jié)點(diǎn)的權(quán)并未丟失。
最后也就是，在拓展霍夫曼樹的時(shí)候，只要堆大小大于2，就累加最小的兩個(gè)點(diǎn)的值。
然后更囧的事發(fā)生了，我手寫的堆超時(shí)了。。。。。
我還用這個(gè)模板ac過pku3013，那個(gè)只能手寫堆才能過的dijkstra。
我記得我這個(gè)堆的寫法是自己想的，當(dāng)初看過一個(gè)stl中的make_heap,pop_heap,push_heap的調(diào)用，在
http://support.microsoft.com/kb/157157/zh-cn
其中有幾行是這樣的
push_heap(Numbers.begin(), Numbers.end()) ;
// you need to call make_heap to re-assert the
// heap property
make_heap(Numbers.begin(), Numbers.end()) ;
現(xiàn)在一看，這幾句寫錯(cuò)了啊。
push_heap之后再make_heap復(fù)雜度就不對(duì)了啊。
其實(shí)應(yīng)該是在堆的末尾插入一個(gè)元素，沿著這個(gè)這個(gè)元素不斷上翻，達(dá)到維護(hù)堆的性質(zhì)的目的,而不是調(diào)用
heapify().
可嘆阿，到今天才寫對(duì)第一個(gè)push_heap();
1
2
3 const int N = 500100;
4 #define L(x) ((x) << 1)
5 #define R(x) (((x) << 1) + 1)
6 #define P(x) ((x) >> 1)
7
8 LL a[N],res; //a從1開始存儲(chǔ)
9 int n;
10
11 void heapify(int x)
12 {
13 int smallest = x,l = L(x),r = R(x);
14 if (l <= n && a[l] < a[smallest]) { smallest = l; }
15 if (r <= n && a[r] < a[smallest]) { smallest = r; }
16 if (smallest != x) {
17 swap(a[smallest],a[x]);
18 heapify(smallest);
19 }
20 }
21
22 LL pop()
23 {
24 swap(a[1],a[n--]);
25 heapify(1);
26 return a[n+1];
27 }
28
29 void make_heap()
30 {
31 for (int i = P(n); i >= 1; i--) {
32 heapify(i);
33 }
34 }
35
36 void push(LL x)
37 {
38 int i = n+1;
39 for (a[++n] = x;i > 1 && a[P(i)] > x; i/= 2) {
40 a[i] = a[P(i)];
41 }
42 a[i] = x;
43 }
44
45 int main()
46 {
47 int i,j,k;
48 scanf("%d",&n);
49 for (i = 1; i < n + 1; i++) {
50 scanf("%I64d",a + i);
51 //cin >> a[i];
52 }
53 make_heap();
54 while (n > 1) {
55 LL a = pop();
56 LL b = pop();
57 res += a + b;
58 push(a + b);
59 }
60 cout << res << endl;
61 return 0;
62 }
63
64