40 40 votes The characters $a$ to $h$ have the set of frequencies based on the first $8$ Fibonacci numbers as follows $a : 1$, $b : 1$, $c : 2$, $d : 3$, $e : 5$, $f : 8$, $g : 13$, $h : 21$ A Huffman code is used to represent the characters. What is the sequence of characters corresponding to the following code? $110111100111010$ $fdheg$ $ecgdf$ $dchfg$ $fehdg$ Algorithms gateit-2006 algorithms greedy-algorithms normal huffman-code + – Ishrat Jahan 19.9k views answer comment Share Follow Print 0 reply Please log in or register to add a comment.
Best answer 61 61 votes Answer is A. Huffman's tree is as follows. The two least frequent characters are taken as the children of a newly made node and the frequency of the newly made node is made equal to the sum of those two child nodes. Then the same procedure is repeated till all nodes are finished. $110111100111010 = 110\;11110\;0\;1110\;10 = fdheg$ Arjun answered Jan 14, 2015 • edited Jul 2, 2019 by Lakshman Bhaiya Arjun comment Share Follow See all 13 Comments 13 13 Comments reply Show 10 previous comments s_dr_13 commented Jul 26, 2020 reply Follow flag How did you draw the tree directly ? 0 0 replyShare thewolf commented Oct 11, 2020 reply Follow flag I think that c will be left child and ab will be right, although it doesn’t matter here. But, insertion in min heap says that, we will insert at the leaf and bubble up till node’s value is greater than or EQUAL to the parent. In that case, c is already the root node and we are inserting ab with value 2. So, after successful bubble up, ab will not be the root, but “c” will be the root and first extract-min will yield “c” as the left child and “ab” as the right child. So, the huffman tree overall will be a skewed one and not the one you’ve shown in answer, but theoretically it doesn’t matter anyway, but to be precise, “c” will be the left child and not the right child. 2 2 replyShare pavansan commented Jan 3, 2025 reply Follow flag another simple way is centre should be highest and centre should come when we add left and right and left should be low value and right should be higher than left so a option is true and d option is wrong because d should be left and e should be right because d value is low and e value is higher 0 0 replyShare Please log in or register to add a comment.
12 12 votes we apply greedy algorithm on the frequencies of the characters to generate the binary tree.Assigning 0 to the left edge and 1 to the right edge. prefix codes for the characters are... a – 1111110 b – 1111111 c – 111110 d – 11110 e – 1110 f – 110 g – 10 h – 0 Given String can be decomposed as fdheg. Answer is A. Mostafize Mondal answered Sep 15, 2018 Mostafize Mondal comment Share Follow See all 2 Comments 2 2 Comments reply Shubham Aggarwal commented Nov 19, 2018 reply Follow flag i think it is better answer and good approch. 0 0 replyShare Nalinj commented Dec 16, 2024 reply Follow flag why not give h 1? and rest 0? 0 0 replyShare Please log in or register to add a comment.
