作者befdawn (蜜蜂P助)
看板Grad-ProbAsk
標題[理工] 離散 Huffman algo 筆記
時間Thu Oct 4 00:42:33 2018
https://i.imgur.com/gArngyY.png
https://i.imgur.com/U2tVfHL.png
請問離散 7.5 這邊，
第二張圖最後面提到的 stable 法，
是如果 merge 出的結果跟原數列中數值相同時，
把結果放到現有數值前嗎？
（像是第一張圖 merge 的狀況，出現了 12 重複的時候 merge 結果放到前面，
所以後來還原的時候是左邊的 12 長出 subtree）
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 106.105.90.47
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1538584955.A.21B.html
1F：推 gpsmelody07: 我手邊的網路筆記是寫將merge後值插入原有數值後方較 10/05 14:55
2F：→ gpsmelody07: stable。不過Huffman tree本來就不唯一，考試題目沒 10/05 14:56
3F：→ gpsmelody07: 規定的話，應該都ok吧(?) 10/05 14:56
4F：推 skyHuan: 應該是前方吧(?) 10/05 14:59
5F：→ skyHuan: 是不是跟sort的stable感覺有點像，原本在前面的如果一樣 10/05 15:01
6F：→ skyHuan: 大不會被搬到後面，5,7原本在12的前面，加起來變12*應該 10/05 15:01
7F：→ skyHuan: 還是要在12前面(? 10/05 15:01
8F：推 gpsmelody07: Cormen只寫使用min-priority queue來extract，並沒有 10/05 19:07
9F：→ gpsmelody07: 特定指是使用何種方法來sort。網路上我查到的case大 10/05 19:07
10F：→ gpsmelody07: 多也都是將合併後的數值放在前面，也許筆記有誤(?) 10/05 19:07
11F：→ befdawn: 黃上課是說他用的方式是 stable 的(也就是放前方) 10/09 13:55