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