How the heap is used as a priority queue to form the Huffman tree. (c)Samuel Marateck original array A8 B3 C9 Z5 E11 D7 A8 / \ original configuration MAX = 6 B3 C9 / \ / Z5 E11 D7 A8 / \ shift down starting with node 3 (C9), resulting in: B3 D7 * / \ / Z5 E11 C9 A8 * / \ The subtree with parent node 2 (B3) is in min-heap form. B3 D7 Shift down from node 1 (A8) / \ / Z5 E11 C9 B3 / \ Continue shift down with node 2 * A8 D7 / \ / Z5 E11 C9 B3 / \ Array is now a min-heap. Z5 D7 / \ / A8 E11 C9 Replace B3 with C9. B3 C9 / \ The array is a heap except for top. So shift down Z5 D7 Since Z5 < D7 exchange Z5 and C9 / \ A8 E11 Z5 / \ Continue shift down. Since A8 < E11 , compare A8 with C9 & switch C9 D7 / \ A8 E11 Z5 Array is now a heap. Replace Z5 with E11. / \ A8 D7 / \ C9 E11 B3 Z5 E11 Shift down / \ A8 D7 / C9 D7 Array is now a heap / \ A8 E11 / C9 form a treelet from B3 Z5. Note that // and \\ are used to display the treelet, whereas, / and \ are used to represent the array. \$8 // \\ insert in last element of array and shift up B3 Z5 D7 and shift up from node 5 / \ A8 E11 / \ C9 \$8 remove D7 and replace with \$8 D7 \$8 and shift down / \ A8 E11 / C9 remove \$8 and replace with C9 D7 \$8 C9 and shift down / \ A8 E11 A8 / \ C9 E11 form treelet \$15 // \\ D7 \$8 place in last position of array and shift up A8 / \ C9 E11 / \$15 The array is a heap. Remove A8 and replace with \$15. A8 \$15 shift down / \ C9 E11 C9 The array is a heap. Remove C9 and replace w/E11 / \ \$15 E11 A8 C9 E11 / \$15 Form the treelet \$17 // \\ A8 C9 and insert it as the last element in the array and shift up. E11 / \ \$15 \$17 Remove E11 and replace it with \$17 E11 \$17 / \$15 shift down E11 \$15 / \$17 remove \$15 E11 \$15 \$17 form treelet \$26 // \\ E11 \$15 Insert in the heap array and shift up \$17 / \$26 Remove both nodes and form treelet \$43 // \\ \$17 \$26 You have now constructed the Huffman tree. To see, however, what it looks like, let's manually construct it. First, we'll list all the treelets \$8 // \\ B3 Z5 \$15 // \\ D7 \$8 \$17 // \\ A8 C9 \$26 // \\ E11 \$15 ------------------------------------------------------------------- Note the following is not an array but is a tree. \$43 // \\ \$17 \$26 // \\ // \\ A8 C9 E11 \$15 // \\ D7 \$8 // \\ B3 Z5 or * // \\ * * // \\ // \\ A8 C9 E11 * // \\ D7 * // \\ B3 Z5 so, the Huffman codes are: A:00 C:01 E:10 D:110 B:1110 Z:1111 ---------------------------------------------------------------- Why do we insert the treelet formed by the two heap mins at the node pointed to by last, and then shift up ? Let's assume the heap is D7 / \ A8 E11 / \ C9 \$8 and we insert \$2 at node 6. So the configuration is: D7 / \ A8 E11 / \ / C9 \$8 \$2 The shifting up procedure first yields D7 / \ A8 \$2 / \ / C9 \$8 E11 and finally: \$2 / \ A8 D7 / \ / C9 \$8 E11 So the configuration is now a heap.