This was suggested by Figure 11.9 in Robert Sedgewick's Algorithms in C++ (1992), p. 157.
During the "heapify" phase, bold face denotes heap cells participating in the downHeap operation, while italics indicate cells within valid subheaps from prior downHeap operations.
During the sorting phase, bold face denotes heap cells currently within the heap, while italics indicate cells that have been removed from the heap.
Current char. array: R O B E R T S E D G E W I C K
R
O B
E R T S
E D G E W I C K
After downHeap(6) [No change]
Current char. array: R O B E R T S E D G E W I C K
R
O B
E R T S
E D G E W I C K
After downHeap(5) [Update]
Current char. array: R O B E R W S E D G E T I C K
R
O B
E R W S
E D G E T I C K
After downHeap(4) [No change]
Current char. array: R O B E R W S E D G E T I C K
R
O B
E R W S
E D G E T I C K
After downHeap(3) [No change]
Current char. array: R O B E R W S E D G E T I C K
R
O B
E R W S
E D G E T I C K
After downHeap(2) [Update]
Current char. array: R O W E R T S E D G E B I C K
R
O W
E R T S
E D G E B I C K
After downHeap(1) [Update]
Current char. array: R R W E O T S E D G E B I C K
R
R W
E O T S
E D G E B I C K
After downHeap(0) [Update]
Current char. array: W R T E O R S E D G E B I C K
W
R T
E O R S
E D G E B I C K
After removing W
Current char. array: T R S E O R K E D G E B I C W
T
R S
E O R K
E D G E B I C W
After removing T
Current char. array: S R R E O I K E D G E B C T W
S
R R
E O I K
E D G E B C T W
After removing S
Current char. array: R O R E G I K E D C E B S T W
R
O R
E G I K
E D C E B S T W
After removing R
Current char. array: R O K E G I B E D C E R S T W
R
O K
E G I B
E D C E R S T W
After removing R
Current char. array: O G K E E I B E D C R R S T W
O
G K
E E I B
E D C R R S T W
After removing O
Current char. array: K G I E E C B E D O R R S T W
K
G I
E E C B
E D O R R S T W
After removing K
Current char. array: I G D E E C B E K O R R S T W
I
G D
E E C B
E K O R R S T W
After removing I
Current char. array: G E D E E C B I K O R R S T W
G
E D
E E C B
I K O R R S T W
After removing G
Current char. array: E E D B E C G I K O R R S T W
E
E D
B E C G
I K O R R S T W
After removing E
Current char. array: E E D B C E G I K O R R S T W
E
E D
B C E G
I K O R R S T W
After removing E
Current char. array: E C D B E E G I K O R R S T W
E
C D
B E E G
I K O R R S T W
After removing E
Current char. array: D C B E E E G I K O R R S T W
D
C B
E E E G
I K O R R S T W
After removing D
Current char. array: C B D E E E G I K O R R S T W
C
B D
E E E G
I K O R R S T W
After removing C
Current char. array: B C D E E E G I K O R R S T W
B
C D
E E E G
I K O R R S T W
No further operations: only one cell remains in the MaxHeap — the smallest element
HeapDemo.java Source code for the program that generated the above example.
HeapDemo.rtf Word
processor file showing the result of processing
"ROBERTSEDGEWICK"
HeapDemo.html Page
showing the result of processing "ASORTINGEXAMPLE"