[理工] 离散 7-5 Huffman algo AAQ8 PTT批踢踢实业坊

楼主: AAQ8 (不要就是要) 2018-10-12 15:32:27

https://i.imgur.com/98ft7IF.jpg
https://i.imgur.com/aIfwLfC.jpg
这题(a)的Huffman tree不知道是不是唯一
因为我画出来的跟答案不一样
不过总bit数都是10
不知道哪里想错了
麻烦各位一下感恩

作者: skyHuan (Huan) 2018-10-12 16:08:00

两个都对，Huffman答案可能不唯一，所以一般都会采stable的方法，就是遇到值一样的node会摆前面https://imgur.com/mGBWqVd.jpg算出来成本都会一样

楼主: AAQ8 (不要就是要) 2018-10-12 16:28:00

所以课本答案采用的是stable的作法?

作者: skyHuan (Huan) 2018-10-12 16:32:00

是的，老师上课也有说用stable比较好答案会跟出题老师想的一样

楼主: AAQ8 (不要就是要) 2018-10-12 16:41:00

好哦感谢你

作者: befdawn (橙花雨露) 2018-10-12 23:49:00

话说我看到洪兔都放后面XD 实在不知道哪个比较stable

作者: skyHuan (Huan) 2018-10-13 00:51:00

我记得洪逸没有特别讲stable子嘉才有强调，stable应该是放前面没错，sort的stable也是放前面实作上应该要看用什么DS，如果用min heap，好像可能会unstable

作者: befdawn (橙花雨露) 2018-10-13 01:21:00

s大是说，后面可能stable吗？

作者: skyHuan (Huan) 2018-10-13 01:51:00

你说最后一句吗？实作会不会stable是看用什么资料结构决定，一次要删两个min可能会用min heap，如果用heap应该有可能不stable，就是原本在前面的跑到后面去

继续阅读