Why so serious? --[NKU]schindlerlee

2010年02月13日星期六.sgu203 二叉堆

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 


posted on 2010-02-13 02:20 schindlerlee 阅读(1369) 评论(0)  编辑 收藏 引用 所属分类: 解题报告


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理