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

else
done = true ;
} // end while
heap[rootIndex] = orphan;
} // end reheap

In the worst case, the method reheap follows a path from the root to a leaf. The number of
nodes along this path is less than or equal to the height h of the heap. Thus, reheap is O( h ). Recall
that the height of a complete n -node tree is log 2 ( n + 1) rounded up, so reheap is an O(log n )
operation.

26.12

The method removeMax . The method removeMax replaces the heap's root with its last leaf to form a
semiheap like the one in Figure 26-6a. The method then calls reheap to transform the semiheap
back into a heap. Thus, removeMax has the following implementation:

public T removeMax()
{

T root = null ;
if (!isEmpty())
{

root = heap[1]; // return value
heap[1] = heap[lastIndex]; // form a semiheap
lastIndex--; // decrease size

reheap(1); // transform to a heap

} // end if
return root;
} // end removeMax
Since reheap is an O(log n ) operation in the worst case, so is removeMax .

Note: To remove a heap's root, you first replace the root with the heap's last leaf. This step
forms a semiheap, so you use the method reheap to transform the semiheap to a heap.

Creating a Heap

26.13

Using add . We could create a heap from a collection of objects by using the add method to add each
object to an initially empty heap. Figure 26-7 shows the steps that this approach would take to add
20, 40, 30, 10, 90, and 70 to a heap. Since add is an O(log n ) operation, creating the heap in this
manner would be O( n log n ).
Notice that we have a heap after each addition. This process does more than we really need.
With less work, we can create one heap from a collection of objects without maintaining a heap at
each intermediate step, as the next segment shows.