Java Reference
In-Depth Information
advanced operations:
decreaseKey and merge
21.4
In Chapter 23 we examine priority queues that support two additional oper-
ations. The decreaseKey operation lowers the value of an item in the priority
queue. The item's position is presumed known. In a binary heap this opera-
tion is easily implemented by percolating up until heap order is reestab-
lished. However, we must be careful because by assumption each item's
position is being stored separately, and all items involved in the percolation
have their positions altered. It is possible to incorporate decreaseKey into the
PriorityQueue class. This is left as Exercise 21.30. The decreaseKey operation
is useful in implementing graph algorithms (e.g., Dijkstra's algorithm pre-
sented in Section 14.3).
The merge routine combines two priority queues. Because the heap is
array-based, the best we can hope to achieve with a merge is to copy the items
from the smaller heap to the larger heap and do some rearranging. Doing so
takes at least linear time per operation. If we use general trees with nodes con-
nected by links, we can reduce the bound to logarithmic cost per operation.
Merging has uses in advanced algorithm design.
internal sorting: heapsort
21.5
A priority queue
can be used to sort
in O ( N log N ) time.
An algorithm based
on this idea is
heapsort .
The priority queue can be used to sort N items by the following:
1.
Inserting every item into a binary heap
2.
Extracting every item by calling deleteMin N times, thus sorting the result
Using the observation in Section 21.4, we can more efficiently implement this
procedure by
1.
Tossing each item into a binary heap
2.
Applying buildHeap
3.
Calling deleteMin N times, with the items exiting the heap in sorted order
Step 1 takes linear time total, and step 2 takes linear time. In step 3, each call
to deleteMin takes logarithmic time, so N calls take O ( N log N ) time. Conse-
quently, we have an O ( N log N ) worst-case sorting algorithm, called heapsort,
which is as good as can be achieved by a comparison-based algorithm (see
Section 8.8). One problem with the algorithm as it stands now is that sorting
 
 
 
Search WWH ::




Custom Search