Develope a Huffman code for the input string a fast runner need never be afraid of the dark?

Answer 1

Algorithm Huffman(X):

Input: String X of length n with d distinct characters

Output: Coding tree for X

Compute the frequency f(c) of each character c of X

Initialize a priority queue Q

for each character c in X do

Create a single-node binary tree T storing c

Insert T into Q with key f(c)

while Q.size() >= 1 do

f1 <- Q.min().key()

T1 <- Q.removein()

f2 <- Q.min().key()

T2 <- Q.removeMin()

Create a new binary tree T with left subtree T1 and right subtree T2

Isert T into Q with f1 + f2

return tree Q.removeMin()