[FSL]Class版二叉堆(2010-09-23 更新)

紫苏

嗯，是 C 写的
不知 unshift 你是怎么测的？九楼那样测一次能看出来的话，反而不正常了，可以这样测：

1. DATA = 10000
   
2. 
   
3. a=[]
   
4. DATA.times { |i| a << i }
   
5. b=[1]
   
6. 
   
7. t1=Time.now
   
8. DATA.times { a.unshift(0) }
   
9. p Time.now-t1
   
10. 
    
11. t2=Time.now
    
12. DATA.times { b.unshift(0) }
    
13. p Time.now-t2

复制代码

一万以内都有明显的差别

-------------------

传递块那个其实是在搞函数式编程时养成习惯了 = = 实际上会影响效率的，因为 Ruby 块符合闭包的上下文绑定特性，这是个昂贵的过程。如果用默认传递的块（即不使用 & 保存到参数，使得块只能对当前方法的局部上下文起作用）的话会好一点

汗，打到这里才想起可以传递 Method 对象，因为没有绑定……但用起来自然是没有块惬意了

紫苏

嗯，但指针是连续内存...
shift 确实只是增加指针：

1. 00480 /*
   
2. 00481  *  call-seq:
   
3. 00482  *     array.shift   ->   obj or nil
   
4. 00483  *  
   
5. 00484  *  Returns the first element of <i>self</i> and removes it (shifting all
   
6. 00485  *  other elements down by one). Returns <code>nil</code> if the array
   
7. 00486  *  is empty.
   
8. 00487  *     
   
9. 00488  *     args = [ "-m", "-q", "filename" ]
   
10. 00489  *     args.shift   #=> "-m"
    
11. 00490  *     args         #=> ["-q", "filename"]
    
12. 00491  */
    
13. 00492
    
14. 00493 VALUE
    
15. 00494 rb_ary_shift(ary)
    
16. 00495     VALUE ary;
    
17. 00496 {
    
18. 00497     VALUE top;
    
19. 00498
    
20. 00499     rb_ary_modify_check(ary);
    
21. 00500     if (RARRAY(ary)->len == 0) return Qnil;
    
22. 00501     top = RARRAY(ary)->ptr[0];
    
23. 00502     ary_make_shared(ary);
    
24. 00503     RARRAY(ary)->ptr++;         /* shift ptr */
    
25. 00504     RARRAY(ary)->len--;
    
26. 00505
    
27. 00506     return top;
    
28. 00507 }

复制代码

不过就像我说的，unshift 和 pop 则会在缓冲区容量不够的时候重新分配内存：

1. 00509 VALUE
   
2. 00510 rb_ary_unshift(ary, item)
   
3. 00511     VALUE ary, item;
   
4. 00512 {
   
5. 00513     rb_ary_modify(ary);
   
6. 00514     if (RARRAY(ary)->len == RARRAY(ary)->aux.capa) {
   
7. 00515         long capa_inc = RARRAY(ary)->aux.capa / 2;
   
8. 00516         if (capa_inc < ARY_DEFAULT_SIZE) {
   
9. 00517             capa_inc = ARY_DEFAULT_SIZE;
   
10. 00518         }
    
11. 00519         RARRAY(ary)->aux.capa += capa_inc;
    
12. 00520         REALLOC_N(RARRAY(ary)->ptr, VALUE, RARRAY(ary)->aux.capa);
    
13. 00521     }
    
14. 00522
    
15. 00523     /* sliding items */
    
16. 00524     MEMMOVE(RARRAY(ary)->ptr + 1, RARRAY(ary)->ptr, VALUE, RARRAY(ary)->len);
    
17. 00525
    
18. 00526     RARRAY(ary)->len++;
    
19. 00527     RARRAY(ary)->ptr[0] = item;
    
20. 00528
    
21. 00529     return ary;
    
22. 00530 }

复制代码

这里的 REALLOC_N 就是包装了 xrealloc 的一个宏；下面还有一个的 MEMMOVE 用来把数组整体右移一位，之后空出来的第一位被设为 unshift 的参数。一般类似这种插入删除的运算，都需要 O(n)，只不过由于按块转移内存，所以效率损失微乎其微
pop 的：

1. 00444 VALUE
   
2. 00445 rb_ary_pop(ary)
   
3. 00446     VALUE ary;
   
4. 00447 {
   
5. 00448     rb_ary_modify_check(ary);
   
6. 00449     if (RARRAY(ary)->len == 0) return Qnil;
   
7. 00450     if (!FL_TEST(ary, ELTS_SHARED) &&
   
8. 00451             RARRAY(ary)->len * 2 < RARRAY(ary)->aux.capa &&
   
9. 00452             RARRAY(ary)->aux.capa > ARY_DEFAULT_SIZE) {
   
10. 00453         RARRAY(ary)->aux.capa = RARRAY(ary)->len * 2;
    
11. 00454         REALLOC_N(RARRAY(ary)->ptr, VALUE, RARRAY(ary)->aux.capa);
    
12. 00455     }
    
13. 00456     return RARRAY(ary)->ptr[--RARRAY(ary)->len];
    
14. 00457 }

复制代码

也需要在适当时候重新分配内存，只不过这次是缩减容量

to_s 那个是写过无数次的二叉树 ASCII 化 + -90度旋转...

紫苏

回复 小幽的马甲 的帖子

可以用来实现原地的堆排序 o.o
不过最大的应用还是实现优先队列，有了优先队列后可以用于离散的事件、消息队列（模拟各种带优先权的队列模型）等，Dijkstra、A*、SMA* 也都是其应用；Prim 可以用二叉堆来表示图，但追求效率就应该用 Fibonacci 堆
至于和 sort 的不同，在于堆比较重视最值，所以省略了很多不需要的排序步骤，各种运算过程都是比排序高效的

小幽的马甲

不过RGSS会有什么要用到堆？Dijkstra或是Prim么……
大家都习惯Array.sort!了呢= =
不过我希望能有人写个菲波那契堆{:nm_9:}

紫苏

使用面向对象的思想的话，自然得用类而不是模块了 ^^

关于初始化：
这里用的是 Array#sort 对数组进行排序，其实并非最优的算法。
可以试想，二叉堆同级的节点并不需要从左到右的顺序（即同级节点顺序可以是混乱的），而排序会保证同级节点的顺序，这显然是多此一举，可以避免，能节省不少步骤。目前最流行的方法是先把数据放在数组中，不用考虑顺序，然后在初始化二叉堆时用删除二叉堆元素的那个 max-heapify 算法（基本上可以看作这里的 dequeue 的一个归纳算法），从二叉堆底部有子节点的节点开始迭代，一直到头部，整个过程完了以后就得到了一个合法的二叉堆了。
Ruby 数组使用的是快速排序，平均时间是 O(n log n)，而使用 max-heapify 的二叉堆建立算法，网上能找到证明了时间是 O(n) 的文章。刚才在 Ruby 层也写了一个 BinaryHeap，实测时毫不意外地发现 max-heapify 的方法比 sort 的方法慢得多。Ruby 1.8 低效率的 GC 和无优化纯解释的性质也不是新闻了，用 Ruby 1.8 写出来的这种数据结构底层接口，性能是比较糟糕的，不可能和 Array#sort 这样的 C 函数比效率，如果是需要大量使用的类库，还得靠 DLL 接口提升性能。后来实测了一下，在 DLL 里相同的 max-heapify 算法确实比 quick sort 的方法快了不少，大概也就是 log n 的因子，而且同时也试了一下用循环把元素添加到二叉堆的方法，比 quick sort 慢不了多少（而在 Ruby 中这么做是和 quick sort 有天壤之别的，虽然两个理论上都是 O(n log n）），沉影不妨一试

关于 enqueue：
这里其实可以不用每次都交换变量。平行赋值用起来倒简洁，但解释器在解释的时候还不是只能用临时变量来实现。以前写插入排序时发现了一个有趣的现象：如果每次把未排序的元素取出时通过交换变量的值插入到排好序的元素中，其效率远远不及用一个临时变量记录这个需要插入的元素，然后让排好序的元素依次向需要插入的元素的方向移动，直到腾出了需要插入的元素的位置为止，之后可以直接把元素放于这个位置。这个现象站在汇编层的角度来想也是合理的：每次通过临时变量交换变量都需要使用三个寄存器，使用三次 mov 指令，而位移只需要开头、结尾的各一次的 mov，中间每次用来位移的 mov 只有一次，代码长度的差别还是比较明显的。这里我们需要让新加入的元素插入到堆中一个满足条件的位置，其思想和插入排序是一致的：让应该放置在新插入的元素下面的父节点依次下移，直到找到一个应该在新插入元素上面的父节点为止，这时就可以直接把新插入的元素放到最后一个下移的父节点之前的位置。

关于 dequeue，这行会影响效率：

1. @data.unshift @data.pop

复制代码

unshift 会调用 memove 拷贝内存重新分配空间，而之后的 pop 则会调用 xrealloc 重新分配内存。这两个操作用经典的算法理论分析都是 O(n) 时间，虽然实际上是很快的，但并非快到可以忽视的地步，毕竟 dequeue 还是可能会频繁调用的。这里可以避免使用 shift 和 unshift 方法，直接 pop，把结果放到 arr[0]

另外吐槽一下二叉堆的基本运算名称数量，一个简单的 `add' 就能概括的事，非要取一大堆 sift-up、bubble-up、heapify-up 之类的名字显得专业 >.>
话说这里用的 enqueue 和 dequeue 使得结构看起来基本和优先队列没有区别了……

附一份刚写的，初始化部分比较慢，原因之前说了：

1. class BinaryHeap
   
2.   def initialize(*args, &cmptr)
   
3.     @cmptr = cmptr
   
4.     @heap = args.clone
   
5.     i = (@heap.size - 1) >> 1
   
6.     while i >= 0
   
7.       max_heapify(i)
   
8.       i -= 1
   
9.     end
   
10.   end
    
11.   def add(elem)
    
12.     i = @heap.size                                  # 当前节点索引
    
13.     loop do
    
14.       j = (i - 1) >> 1                              # 父节点索引
    
15.       if j < 0 || @cmptr.call(elem, @heap[j]) <= 0  # 顺序正确
    
16.         @heap[i] = elem
    
17.         break
    
18.       else                                          # 顺序不正确
    
19.         @heap[i] = @heap[j]
    
20.         i = j
    
21.       end
    
22.     end
    
23.     self
    
24.   end
    
25.   def shift(idx = 0)
    
26.     ret = @heap[idx]
    
27.     len = @heap.size
    
28.     if len > 1
    
29.       @heap[idx] = @heap.pop
    
30.       max_heapify(idx)
    
31.     elsif 1 == len then @heap.clear
    
32.     end
    
33.     ret
    
34.   end
    
35.   def max_heapify(idx)
    
36.     len = @heap.size
    
37.     loop do
    
38.       i = (idx << 1) + 1                            # 左子节点
    
39.       j = i + 1                                     # 右子节点
    
40.       max = idx
    
41.       max = j if j < len &&
    
42.         @cmptr.call(@heap[j], @heap[max]) > 0
    
43.       max = i if i < len &&
    
44.         @cmptr.call(@heap[i], @heap[max]) > 0
    
45.       if max != idx
    
46.         @heap[idx],@heap[max] =
    
47.         @heap[max],@heap[idx]
    
48.         idx = max
    
49.       else
    
50.         break
    
51.       end
    
52.     end
    
53.   end
    
54.   def to_s(indent = 8)
    
55.     helper = lambda do |idx, acc|
    
56.       if idx >= @heap.size then ''
    
57.       else
    
58.         child_base = idx << 1
    
59.         helper.call(child_base + 2, acc + 1) +
    
60.         ' '*indent*acc + @heap[idx].to_s + "\n" +
    
61.         helper.call(child_base + 1, acc + 1)
    
62.       end
    
63.     end
    
64.     helper.call(0, 0)
    
65.   end
    
66.   def <<(elem)
    
67.     add(elem)
    
68.   end
    
69. end
    
70. 
    
71. DATA = 10
    
72. data = Array.new(DATA)
    
73. DATA.times do |i|
    
74.   data[i] = rand(DATA<<1)
    
75. end
    
76. 
    
77. bh = BinaryHeap.new(*data) { |a, b| a <=> b }
    
78. print bh
    
79. bh << 1 << 3 << 0 << -3 << 0
    
80. print bh
    
81. bh.shift
    
82. print bh
    
83. bh.shift
    
84. print bh

复制代码