A Heap Implementation - Data Structures and Abstractions with Java - page 676

int newIndex = lastIndex;
int parentIndex = newIndex / 2;
while ( (parentIndex > 0) && newEntry.compareTo(heap[parentIndex]) > 0)
{

heap[newIndex] = heap[parentIndex];
newIndex = parentIndex;
parentIndex = newIndex / 2;
} // end while
heap[newIndex] = newEntry;
} // end add

We can omit the test of parentIndex in the while statement if we place a sentinel value in
the unused array location at index 0. We can use newEntry as this sentinel. You should answer
Question 5 and convince yourself that this change will work.
In the worst case, this method follows a path from a leaf to the root. In Segment 23.9 of
Chapter 23, we saw that the height of a complete tree having n nodes is log 2 ( n + 1) rounded up.
Thus, the add method is an O(log n ) operation in the worst case.

Question 4 Define the private method ensureCapacity .
Question 5 Revise the previous method add by placing newEntry as a sentinel value in
the unused array location at index 0. You then can omit the test of parentIndex in the
while statement.

Removing the Root

26.9

The basic algorithm. The removeMax method for a maxheap removes and returns the heap's largest
object. This object is in the root of the maxheap. Let's remove the entry in the root of the heap in
Figure 26-3d. Figure 26-5a shows this heap as if its root was empty.
We do not want to rip the root node out of the heap, as this will leave two disjoint subtrees.
Instead we remove a leaf, namely the last one in the heap. To do so, we copy the leaf's data—30—to
the root and then remove the leaf from the tree, as Figure 26-5b illustrates. Of course, in the array-
based implementation, removing this leaf simply means adjusting lastIndex .
The 30 is out of place, so we no longer have a heap. We let the 30 sink down to its correct loca-
tion. As long as 30 is less than its children, we swap it with its larger child. Thus, in Figure 26-5c,
we have swapped 30 and 85. Continuing, we swap 30 and 80, as Figure 26-5d shows. In this case
the 30 has settled at a leaf. In general, the out-of-place entry will settle at a node whose children are
not greater than the entry.

Question 6 What steps are necessary to remove the root from the heap in Figure 26-5d?

26.10

Transforming a semiheap into a heap. The tree in Figure 26-5b is called a semiheap . Except for
the root, the objects in a semiheap are ordered as they are in a heap. In removing the root of the
heap, we formed a semiheap and then transformed it back into a heap. As in the method add , we
can save time by not swapping entries. Figure 26-6 shows the semiheap from Figure 26-5b and the
steps that transform it into a heap without the swaps.