A priority queue: the binary heap - Data Structures and Problem Solving Using Java - page 825

figure 21.26
Heap after the first
deleteMax operation

59

53 58

26 41 36 31

16 21 97

59 53 58 26 41 36 31 16 21 97 J111213

0 1 2 3 4 5 6 7 8 9 10 11 12 13

Figure 21.27 shows that after a second deleteMax , 16 becomes the last
element. Now only eight items remain in the heap. The maximum element
removed, 59, is placed in the dead spot of the array. After seven more
deleteMax operations, the heap represents only one element, but the elements
left in the array will be sorted in increasing order.

Implementation of the heapsort operation is simple because it basically
follows the heap operation. There are three minor differences between the two
operations. First, because we are using a max heap, we need to reverse the
logic of the comparisons from > to <. Second, we can no longer assume that
there is a sentinel position 0. The reason is that all our other sorting algorithms
store data at position 0, and we must assume that heapSort is no different.
Although the sentinel is not needed anyway (there are no percolate up opera-
tions), its absence affects calculations of the child and parent. That is, for a
node in position i, the parent is in position , the left child is in posi-
tion , and the right child is next to the left child. Third, percDown needs
to be informed of the current heap size (which is lowered by 1 in each itera-
tion of deleteMax ). The implementation of percDown is left for you to do as

Minor changes are
required for heap-
sort because the
root is stored in
position 0.

( i - 1 ) ⁄ 2

2 i + 1

figure 21.27
Heap after the second
deleteMax operation

58

53 36

26 41 21 31

16 59 97

58 53 36 26 41 21 31 16 59 97 J111213

0 1 2 3 4 5 6 7 8 9 10 11 12 13