[理工] 離散 Huffman algo 筆記

[befdawn (蜜蜂P助)]

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1538584955.A.21B.html
推 gpsmelody07: 我手邊的網路筆記是寫將merge後值插入原有數值後方較
→ gpsmelody07: stable。不過Huffman tree本來就不唯一，考試題目沒
→ gpsmelody07: 規定的話，應該都ok吧(?)
推 skyHuan: 應該是前方吧(?)
→ skyHuan: 是不是跟sort的stable感覺有點像，原本在前面的如果一樣
→ skyHuan: 大不會被搬到後面，5,7原本在12的前面，加起來變12*應該
→ skyHuan: 還是要在12前面(?
推 gpsmelody07: Cormen只寫使用min-priority queue來extract，並沒有
→ gpsmelody07: 特定指是使用何種方法來sort。網路上我查到的case大
→ gpsmelody07: 多也都是將合併後的數值放在前面，也許筆記有誤(?)
→ befdawn: 黃上課是說他用的方式是 stable 的(也就是放前方)