1
$\begingroup$

Steps to build Huffman Tree Input is array of unique characters along with their frequency of occurrences and output is Huffman Tree.

  1. Create a leaf node for each unique character and build a min heap of all leaf nodes (Min Heap is used as a priority queue. The value of frequency field is used to compare two nodes in min heap. Initially, the least frequent character is at root)

  2. Extract two nodes with the minimum frequency from the min heap.

  3. Create a new internal node with frequency equal to the sum of the two nodes frequencies. Make the first extracted node as its left child and the other extracted node as its right child. Add this node to the min heap.

  4. Repeat steps#2 and #3 until the heap contains only one node. The remaining node is the root node and the tree is complete.

If we would like to generalize the Huffman algorithm for coded words in ternary system (i.e. coded words using the symbols 0 , 1 and 2 ) I think that we could do it as follows.

Steps to build Huffman Tree Input is array of unique characters along with their frequency of occurrences and output is Huffman Tree.

  1. Create a leaf node for each unique character and build a min heap of all leaf nodes

  2. Extract three nodes with the minimum frequency from the min heap.

  3. Create a new internal node with frequency equal to the sum of the three nodes frequencies. Make the first extracted node as its left child, the second extracted node as its middle child and the third extracted node as its right child. Add this node to the min heap.

  4. Repeat steps#2 and #3 until the heap contains only one node. The remaining node is the root node and the tree is complete.

How can we prove that the algorithm yields optimal ternary codes?

$\endgroup$
  • 2
    $\begingroup$ Have you tried mimicking the optimality proof of the binary case? $\endgroup$ – Yuval Filmus Mar 29 '15 at 2:42
  • 1
    $\begingroup$ Cross-posted on cstheory: cstheory.stackexchange.com/questions/30945/…. $\endgroup$ – Yuval Filmus Mar 29 '15 at 2:46
  • $\begingroup$ Please don't cross-post on multiple SE sites. That is forbidden by site rules, and impolite to authors as it leaves responses spread across two sites. $\endgroup$ – D.W. Mar 29 '15 at 19:10
  • $\begingroup$ Can you please proofread your question? $\endgroup$ – Juho Mar 30 '15 at 6:30
  • $\begingroup$ The D-ary algorithm is described in Cover and Thomas. The question could easily be a homework problem, which asked students to generalize from binary to ternary. And you haven't quite gotten the algorithm correct. Consider a case where you start with an even number of characters. $\endgroup$ – Peter Shor Mar 30 '15 at 20:05
2
$\begingroup$

We can’t prove that, but we can disprove it. The given algorithm is not always optimal. In step 2, three nodes may not be available, so there is more than one way to build the tree. That can’t happen in the binary case.

Consider a min heap containing four characters, whose frequencies are 0.4, 0.3, 0.2, and 0.1. The given algorithm yields the tree on the left, with mean length 1.6. The optimal tree is shown on the right, mean length 1.3.

@PeterShor’s comment above indicates that a correct algorithm is known, but I haven’t seen it.

Ternary Huffman trees

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.