Source code online books for professionals by professionals

weighted balancing: You want the expected number of questions to be as low as possible. You want to minimize the 
expected depth of your (pruned) traversal from root to leaf.
You find that this idea can be used to account for the severity as well. You’d want to prioritize the most dangerous 
conditions so they can be identified quickly (“Is the patient breathing?”), at the cost of making patients with less 
critical ailments wait through a couple of extra questions. You do this, with the help of some health professionals, by 
giving each condition a cost or weight, combining the frequency (probability) and the health risk involved. Your goal 
for the tree structure is still the same. How can you minimize the sum of depth(u) × weight(u) over all leaves u?
This problem certainly has other applications as well. In fact, the original (and most common) application is 
compression—representing a text more compactly—through variable-length codes. Each character in your text has a 
frequency of occurrence, and you want to exploit this information to give the characters encodings of different lengths 
so as to minimize the expected length of any text. Equivalently, for any character, you want to minimize the expected 
length of its encoding.
Do you see how this is similar to the previous problem? Consider the version where you focused only on the 
probability of a given medical condition. Now, instead of minimizing the number of yes/no questions needed to 
identify some medical affliction, we want to minimize the number of bits needed to identify a character. Both the  
yes/no answers and the bits uniquely identify paths to leaves in a binary tree (for example, zero = no = left and  
one = yes = right).
5
 For example, consider the characters a through f. One way of encoding them is given by Figure 
7-2
  
(just ignore the numbers in the nodes for now). For example, the code for g (given by the highlighted path) would 
be 101. Because all characters are in the leaves, there would be no ambiguity when decoding a text that had been 
compressed with this scheme (see Exercise 7-7). This property, that no valid code is a prefix of another, gives rise to 
the term prefix code.
5
Not only is it unimportant whether zero means left or right, it is also unimportant which subtrees are on the left and which are on the 
right. Shuffling them won’t matter to the optimality of the solution.

---

Chapter 7 
■
 Greed Is Good? prove It! 
145
The Algorithm
Let’s start by designing a greedy algorithm to solve this problem, before showing that it’s correct (which is, of course, 
the crucial step). The most obvious greedy strategy would, perhaps, be to add the characters (leaves) one by one, 
starting with the one with the greatest frequency. But where would we add them? Another way to go (which you’ll see 
again in Kruskal’s algorithm, in a bit) is to let a partial solution consist of several tree fragments and then repeatedly 
combine them. When we combine two trees, we add a new, shared root and give it a weight equal to the sum of its 
children, that is, the previous roots. This is exactly what the numbers inside the nodes in Figure 
7-2
 mean.
Listing 7-1 shows one way of implementing Huffman’s algorithm. It maintains a partial solution as a forest, with 
each tree represented as nested lists. For as long as there are at least two separate trees in the forest, the two lightest 
trees (the ones with lowest weights in their roots) are picked out, combined, and placed back in, with a new root weight.