作者AAQ8 ()
看板Grad-ProbAsk
標題[理工] 離散 7-5 Huffman algo
時間Fri Oct 12 15:32:27 2018
https://i.imgur.com/98ft7IF.jpg
https://i.imgur.com/aIfwLfC.jpg
這題(a)的Huffman tree不知道是不是唯一
因為我畫出來的跟答案不一樣
不過總bit數都是10
不知道哪裡想錯了
麻煩各位一下 感恩
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.242.14.186
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1539329549.A.1C6.html
1F：推 skyHuan: 兩個都對，Huffman答案可能不唯一，所以一般都會採stable 10/12 16:08
2F：→ skyHuan: 的方法，就是遇到值一樣的node會擺前面 10/12 16:08
4F：→ skyHuan: 算出來成本都會一樣 10/12 16:09
5F：→ AAQ8: 所以課本答案採用的是stable的作法? 10/12 16:28
6F：→ skyHuan: 是的，老師上課也有說用stable比較好答案會跟出題老師想 10/12 16:32
7F：→ skyHuan: 的一樣 10/12 16:32
8F：→ AAQ8: 好哦 感謝你 10/12 16:41
9F：→ befdawn: 話說我看到洪兔都放後面XD 實在不知道哪個比較stable 10/12 23:49
10F：推 skyHuan: 我記得洪逸沒有特別講stable子嘉才有強調，stable應該是 10/13 00:51
11F：→ skyHuan: 放前面沒錯，sort的stable也是放前面 10/13 00:51
12F：→ skyHuan: 實作上應該要看用什麼DS，如果用min heap，好像可能會uns 10/13 00:51
13F：→ skyHuan: table 10/13 00:51
14F：→ befdawn: s大是說，後面可能stable嗎？ 10/13 01:21
15F：→ skyHuan: 你說最後一句嗎？實作會不會stable是看用什麼資料結構決 10/13 01:51
16F：→ skyHuan: 定，一次要刪兩個min可能會用min heap，如果用heap應該 10/13 01:51
17F：→ skyHuan: 有可能不stable，就是原本在前面的跑到後面去 10/13 01:51