算法分析與設計實踐作業11

1.問題

最優字首編碼

2.解析

構造最優字首碼的貪心算法就是哈夫曼算法

執行個體：

{5，5，10,10,10,15,20,25}

3.設計

算法 Huffman©

輸入：C={x1,x2,…,xn},f(xi),i=1,2,…,n

輸出:Q//隊列

n←|C|

Q←C//頻率遞增隊列Q

for i←1 to n-1 do

z←Allocate-Node()//生成結點

z.left←Q中最小元//最小作z左兒子

z.right←Q中最小元//最小作z右兒子

f(z)←f(x)+f(y)

Insert(Q,z)//将z插入Q

return Q

4.分析

O(nlogn)頻率排序;for循環O(n)，插入操作O(logn)，算法時間複雜度是O(nlogn)

5.源碼

https://github.com/jinwanzaodianshui/zuoye11