※ 引述《windows2k (KERORO军曹)》之铭言： : ※ 引述《march20 ()》之铭言： : : 推 ericbibo:嗯~huffman's algorithm...每次都挑最小的两个出来合并 07/08 21:02 : : 看到 n log n , 大胆猜看看. : : 我猜最佳合并法就是 s_x,...,s_m 和 s_(m+1),...,s_y 先各自合并, 接着再并起来. : 假设有这样一个数列 : 10 7 2 4 12 6 : 用 huffman algorithm : 10 7 6 12 6 cost : 6 : 10 7 12 12 cost : 12 : 12 12 17 cost : 17 : 24 17 cost : 24 : 41 cost : 41 : Total Cost: 100 : 用版大的方法: : Total Sum: 41 : 所以我们要将 : (10 7 2) (4 12 6)分别进行合并 : (10 7 2) Total Cost: 28 : (4 12 6) Total Cost: 38 : 19 22 Cost : 41 : Total Cost: 107 : Optimal Solution: : 10 7 2 4 12 6 : 10 7 6 12 6 cost : 6 : 10 7 6 18 cost : 18 : 10 13 18 cost : 13 : 23 18 cost : 23 : 41 cost : 41 : Total Cost: 101 嗯, 看到这个 case, 给了我一个灵感 (先 po 出来看看) Huffman 找值最小的两个来合并, 这里似乎要找相邻和最小的两数来合并. 比如 10+7, 7+2, 2+4, 4+12, 12+6, 所以先拿 2,4 来合并. 然後 update heap 时, 要将影响到的邻居一并 update 比如第一轮找到 2+4 为最小, 那就把 2+4 pop 出来, 这时影响到的 node 就是 7+2 和 4+12 要将这两个值变成 7+6 和 6+12 然後调整 heap. 现在有两件事要做 1. maintain min-heap, 但同时要让 update 受到影响的 node 而且这个动作只能花 O(lg n) time. 2. 证明这样可以找到 optimal solution. 第二项暂且按下, 先来看第一项. 首先 heap node 的内容得是 (x,y,i,j) 其中 x,y 为某相邻两数 (可能是之前并过的), i,j 为 左右邻居在 heap 中的位置, 然後 node priority 为 x+y 比如 2+4 的 i 就是 7+2 在 heap 中的位置, j 就是 4+12 在 heap 中的位置. 现在 heap 的各构成动作修正如下: 1. Heap initialization: 首先对各相邻两数建出 heap node 并依数列顺序放在 heap array 里, 以上例来说 (10,7,0,2) (7,2,1,3) (2,4,2,4) (4,12,3,5) (12,6,4,0) 其中 0 代表这是最数序中左或最右一组数字. 接下来要调整 heap 内容, 就跟原本的 heap 一样, 但调整 node 时, 要一并调整左右邻居的 i 和 j, 比如在调整 (7,2,1,3) 时, 这个 node 会跟 (12,6,4,0) 对调, 因此 (7,2,1,3) 的位置从 2 变成 5, 所以 (10,7,0,2) (也就是位置是 1 的那个 node) 变成 (10,7,5,2) (2,4,2,4) (也就是位置是 3 的那个 node) 变成 (2,4,5,4) 同样的, (12,6,4,0) 的位置从 5 变成 2, 同时 (4,12,3,5) (也就是位置 4 的那个 node) 变成 (4,12,3,2). 总之, 只要是移动 node 位置的动作, 就要调整左右邻居的 i 和 j 值 (呃, 左右邻居是对原数列来说, 而不是对 heap 来说) 很明类的, 每次移动一个 node, 只需要额外花 constant time 就可以 maintain 跟左右邻居的关系, 整个 initialzation 依然控制在 n lg n time 内 2. Minimum value removal, 跟原来的 removal 相同, 但要 update 左右邻居的值. 有件事要注意, min-value removal 发生在数字合并时. 先拿之前例子 (在 heapify 之前) 的内容来举例, 比如 (10,7,0,2) 被移掉了, 也就是 10 和 7 先被合并, 接下来应该 update node 2 也就是 (7,2,1,3). 应该得变成 (17,2,0,3). (heapify 後 update 的动作跟这一样, 但除了要修正 removal 所导致的空缺外, 还要调整左右邻居的位置, 这个动作要 lg n 的时间). 每个 removal 依然维持在 lg n time. 至於 correctness, 嗯, 有空再来证, 直觉上是对的 (但也有可能是错的 XD) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 71.137.22.103 ※ 编辑: march20 来自: 71.137.22.103 (07/10 09:26) ※ 编辑: march20 来自: 71.137.22.103 (07/10 09:26) ※ 编辑: march20 来自: 71.137.22.103 (07/10 09:27) ※ 编辑: march20 来自: 71.137.22.103 (07/10 09:28)