※ 引述《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)