Java Reference
In-Depth Information
takes for the node being sifted to reach the bottom of the tree. In any complete tree,
approximately half of the nodes are leaves and so cannot be moved downward at
all. One quarter of the nodes are one level above the leaves, and so their elements
can move down at most one level. At each step up the tree we get half the number of
nodes as were at the previous level, and an additional height of one. The maximum
sum of total distances that elements can go is therefore
logn
logn
X
X
(i 1)
n
2
i
=
n
i 1
2
i1
:
2
i=1
i=1
From Equation 2.9 we know that this summation has a closed-form solution of
approximately 2, so this algorithm takes (n) time in the worst case. This is far
better than building the heap one element at a time, which would cost (n log n)
in the worst case. It is also faster than the (n log n) average-case time and (n
2
)
worst-case time required to build the BST.
Removing the maximum (root) value from a heap containing n elements re-
quires that we maintain the complete binary tree shape, and that the remaining
n1 node values conform to the heap property. We can maintain the proper shape
by moving the element in the last position in the heap (the current last element in
the array) to the root position. We now consider the heap to be one element smaller.
Unfortunately, the new root value is probably not the maximum value in the new
heap. This problem is easily solved by using
siftdown
to reorder the heap. Be-
cause the heap is log n levels deep, the cost of deleting the maximum element is
(log n) in the average and worst cases.
The heap is a natural implementation for the priority queue discussed at the
beginning of this section. Jobs can be added to the heap (using their priority value
as the ordering key) when needed. Method
removemax
can be called whenever a
new job is to be executed.
Some applications of priority queues require the ability to change the priority of
an object already stored in the queue. This might require that the object's position
in the heap representation be updated. Unfortunately, a max-heap is not efficient
when searching for an arbitrary value; it is only good for finding the maximum
value. However, if we already know the index for an object within the heap, it is
a simple matter to update its priority (including changing its position to maintain
the heap property) or remove it. The
remove
method takes as input the position
of the node to be removed from the heap. A typical implementation for priority
queues requiring updating of priorities will need to use an auxiliary data structure
that supports efficient search for objects (such as a BST). Records in the auxiliary
data structure will store the object's heap index, so that the object can be deleted
from the heap and reinserted with its new priority (see Project 5.5). Sections 11.4.1
and 11.5.1 present applications for a priority queue with priority updating.
