The Huffman coding tree function buildHuff of Figure 5.29 manipulates a sorted list. This could result in a (Θn²) algorithm, because placing an intermediate Huffman tree on the list could take Θ(n) time. Revise this algorithm to use a priority queue based on a min-heap instead of a list.

In Figure 5.29

Transcribed Image Text:

// Build a Huffman tree from list hufflist static HuffTree buildTree (List hufflist) { HuffTree tmp1, tmp2, tmp3; LettFreq tmpnode; } for (hufflist.moveToPos (1); hufflist.length() > 1; hufflist.moveToPos (1)) { } // While at least two items left hufflist.moveToStart (); tmpl= hufflist.remove(); tmp2 = hufflist.remove(); tmpnode = new LettFreq (tmpl.weight () + tmp2.weight ()); tmp3 = new HuffTree (tmpnode, tmp1, tmp2); // return to the list in sorted order for (hufflist.moveToStart (); hufflist.currPos () < hufflist.length(); hufflist.next()) if (tmp3.weight () = hufflist.length()) hufflist.append (tmp3); // This is heaviest value hufflist.moveToStart (); // This is only tree on list return hufflist.remove(); // Return the tree.