作者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/cn.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