Question

Question 16.3.6: (Introduction to Algorithms 3rd Edition)

Suppose you have an optimal prefix code on a set C = { c0, c1, …, c(n-1) } of characters and you wish to transmit this code using as few bits as possible. Write an algorithm to represent any optimal prefix code on C using only 2n-1+n*⎡lgn⎤bits. (Hint: Use 2n-1 bits to specify the structure of the tree, as discovered by a walk of the tree.)

Answer 1

Solution: The steps used to assign optimal prefix codes are shown below: Build a Huffman tree using input characters . Traverse Huffman tree and assign characters with codes Steps for building Huffman tree For each character that is unique, create a leaf node and for all leaf nodes build a min heap Create a new node internally with frequency that equals to sum of frequencies of two nodes . Make node that is first extracted as left child & other as right child . Add these nodes to min heap Repeat above steps until only single node is present in heap. The node that is remaining is root and tree becomes complete. Example The example is shown below Character Frequency 12 13 16 45

. The Huffman tree is shown below: 100 25 30 14 Time complexity If input array is sorted, algorithm would take linear time. The time complexity of algorithm is O(n logn) where "n" denotes unique character count . The method to find extract minimum is called "2*(n-1)" times and it takes O (log n) time as it calls procedure for min heapify. So, overall complexity is O(n log n).