[理工] 離散 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，就是原本在前面的跑到後面去

繼續閱讀