2010年02月13日星期六.sgu203 二叉堆
sgu203:堆,根據一個文章生成單詞出現次數,求對這個文章進行霍夫曼編碼之后的文章長度。
我郁悶，這個題想了半天，想了一個構建二叉樹，然后記錄葉子節點深度,之后用最大深度減去這
個深度的方法。不過，我自己都覺得這個應該過不了。。。
無意間看了一眼discuss，有一人的代碼寫了這么兩句
a = heap.pop(),b = heap.pop();
ans = ans + a + b;
一拍大腿，原來如此啊，我咋沒想到。。。
霍夫曼樹選擇兩個最小的加到新節點上，那么也就等于到這兩個小的節點的邊就被加到了新節點上。
也就是，隨著新節點的繼續累計，這個兩個節點的權并未丟失。
最后也就是，在拓展霍夫曼樹的時候，只要堆大小大于2，就累加最小的兩個點的值。
然后更囧的事發生了，我手寫的堆超時了。。。。。
我還用這個模板ac過pku3013，那個只能手寫堆才能過的dijkstra。
我記得我這個堆的寫法是自己想的，當初看過一個stl中的make_heap,pop_heap,push_heap的調用，在
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()) ;
現在一看，這幾句寫錯了啊。
push_heap之后再make_heap復雜度就不對了啊。
其實應該是在堆的末尾插入一個元素，沿著這個這個元素不斷上翻，達到維護堆的性質的目的,而不是調用
heapify().
可嘆阿，到今天才寫對第一個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開始存儲
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