[理工] 離散 Huffman algo 筆記

看板Grad-ProbAsk作者 (蜜蜂P助)時間5年前 (2018/10/04 00:42), 編輯推噓3(3推 0噓 8→)
留言11則, 3人參與, 5年前最新討論串1/1
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
推
10/05 14:55, 5年前 , 1F
我手邊的網路筆記是寫將merge後值插入原有數值後方較
10/05 14:55, 1F
→
10/05 14:56, 5年前 , 2F
stable。不過Huffman tree本來就不唯一，考試題目沒
10/05 14:56, 2F
→
10/05 14:56, 5年前 , 3F
規定的話，應該都ok吧(?)
10/05 14:56, 3F
推
10/05 14:59, 5年前 , 4F
應該是前方吧(?)
10/05 14:59, 4F
→
10/05 15:01, 5年前 , 5F
是不是跟sort的stable感覺有點像，原本在前面的如果一樣
10/05 15:01, 5F
→
10/05 15:01, 5年前 , 6F
大不會被搬到後面，5,7原本在12的前面，加起來變12*應該
10/05 15:01, 6F
→
10/05 15:01, 5年前 , 7F
還是要在12前面(?
10/05 15:01, 7F
推
10/05 19:07, 5年前 , 8F
Cormen只寫使用min-priority queue來extract，並沒有
10/05 19:07, 8F
→
10/05 19:07, 5年前 , 9F
特定指是使用何種方法來sort。網路上我查到的case大
10/05 19:07, 9F
→
10/05 19:07, 5年前 , 10F
多也都是將合併後的數值放在前面，也許筆記有誤(?)
10/05 19:07, 10F
→
10/09 13:55, 5年前 , 11F
黃上課是說他用的方式是 stable 的(也就是放前方)
10/09 13:55, 11F
‣ 更多 befdawn 的文章
文章代碼(AID): #1RjF5x8R (Grad-ProbAsk)