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