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

an array requires the use of the binary heap data structure, which itself carries
the overhead of an array. Emulating the heap data structure on the array that is
input—rather than going through the heap class apparatus—would be prefer-
able. We assume for the rest of this discussion that this is done.
Even though we do not use the heap class directly, we still seem to need a
second array. The reason is that we have to record the order in which items
exit the heap equivalent in a second array and then copy that ordering back
into the original array. The memory requirement is doubled, which could be
crucial in some applications. Note that the extra time spent copying the sec-
ond array back to the first is only O ( N ), so, unlike mergesort, the extra array
does not affect the running time significantly. The problem is space.

A clever way to avoid using a second array makes use of the fact that,
after each deleteMin , the heap shrinks by 1. Thus the cell that was last in the
heap can be used to store the element just deleted. As an example, suppose
that we have a heap with six elements. The first deleteMin produces A 1 . Now
the heap has only five elements, so we can place A 1 in position 6. The next
deleteMin produces A 2 . As the heap now has only four elements, we can place
A 2 in position 5.

By using empty
parts of the array,
we can perform the
sort in place.

When we use this strategy, after the last deleteMin the array will contain
the elements in decreasing sorted order. If we want the array to be in the
more typical increasing sorted order, we can change the ordering property
so that the parent has a larger key than the child does. Thus we have a max
heap. For example, let us say that we want to sort the input sequence 59, 36,
58, 21, 41, 97, 31, 16, 26, and 53. After tossing the items into the max heap
and applying buildHeap , we obtain the arrangement shown in Figure 21.25.
(Note that there is no sentinel; we presume the data starts in position 0, as is
typical for the other sorts described in Chapter 8.)
Figure 21.26 shows the heap that results after the first deleteMax . The last
element in the heap is 21; 97 has been placed in a part of the heap array that is
technically no longer part of the heap.

If we use a max
heap, we obtain
items in increasing
order.

figure 21.25
Max heap after the
buildHeap phase

97

53 59

26 41 58 31

16 21 36

97 53 59 26 41 58 31 16 21 36 J111213

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