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.