Page 209 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes In this example, the new item to be inserted has the key 2. Note that you cannot simply drop the
new item into the next position in the complete tree because the resulting tree is no longer heap
ordered. Instead, the hole in the heap is moved toward the root by moving items down in the
heap as shown in Figure 10.3 (b) and (c). The process of moving items down terminates either
when you reach the root of the tree or when the hole has been moved up to a position in which
when the new item is inserted the result is a heap.

Program 10.2 gives the code for inserting an item in a binary heap. The enqueue method of the
BinaryHeap class takes as its argument the item to be inserted in the heap. If the priority queue is
full an exception is thrown. Otherwise, the item is inserted as described above.
public class BinaryHeap
extends AbstractContainer
implements PriorityQueue
{
protected Comparable[] array;
public void enqueue (Comparable object)
{
if (count == array. length - 1)
throw new ContainerFullException ();
++count;
int i == count;
while (i > 1 && array [i/2].isGT (object))
{
array [i] = array [i/2];
i/=2;
}
array [i] = object;
}
//...
}
Program 10.2: BinaryHeap class enqueue Method
The implementation of the algorithm is actually remarkably simple. Lines 13-17 move the hole in
the heap up by moving items down. When the loop terminates, the new item can be inserted at
position i. Therefore, the loop terminates either at the root, i=1, or when the key in the parent of
i, which is found at position ⎣i/2⎦, is smaller than the item to be inserted.
Notice too that a good optimizing compiler will recognize that the subscript calculations involve
only division by two. Therefore, the divisions can be replaced by bitwise right shifts which
usually run much more quickly.
Since the depth of a complete binary tree with n nodes is ⎣log n⎦, the worst case running time for
2
the enqueue operation is
⎣log n⎦, τ(isGT) + O(log n),
2
where τ(isGT) is the time required to compare to objects. If τ(isGT) = O(1), the enqueue operation
is simply O(log n) in the worst case.

204 LOVELY PROFESSIONAL UNIVERSITY