Java Reference
In-Depth Information
basic ideas
21.1
As discussed in Section 6.9, the priority queue supports the access and deletion of
the minimum item with findMin and deleteMin , respectively. We could use a sim-
ple linked list, performing insertions at the front in constant time, but then finding
and/or deleting the minimum would require a linear scan of the list. Alternatively,
we could insist that the list always be kept sorted. This condition makes the access
and deletion of the minimum cheap, but then insertions would be linear.
A linked list or array
requires that some
operation use linear
time.
Another way of implementing priority queues is to use a binary search
tree, which gives an O (log N ) average running time for both operations. How-
ever, a binary search tree is a poor choice because the input is typically not
sufficiently random. We could use a balanced search tree, but the structures
shown in Chapter 19 are cumbersome to implement and lead to sluggish per-
formance in practice. (In Chapter 22, however, we cover a data structure, the
splay tree, that has been shown empirically to be a good alternative in some
situations.)
An unbalanced
binary search tree
does not have a
good worst case. A
balanced search
tree requires lots of
work.
On the one hand, because the priority queue supports only some of the
search tree operations, it should not be more expensive to implement than a
search tree. On the other hand, the priority queue is more powerful than a sim-
ple queue because we can use a priority queue to implement a queue as fol-
lows. First, we insert each item with an indication of its insertion time. Then,
a deleteMin on the basis of minimum insertion time implements a dequeue .
Consequently, we can expect to obtain an implementation with properties that
are a compromise between a queue and a search tree. This compromise is
realized by the binary heap, which
The priority queue
has properties that
are a compromise
between a queue
and a binary search
tree.
Can be implemented by using a simple array (like the queue)
n
Supports insert and deleteMin in O (log N ) worst-case time (a com-
promise between the binary search tree and the queue)
n
Supports insert in constant average time and findMin in constant
worst-case time (like the queue)
n
The binary heap is the classic method used to implement priority queues and—
like the balanced search tree structures in Chapter 19—has two properties: a struc-
ture property and an ordering property. And as with balanced search trees, an opera-
tion on a binary heap can destroy one of the properties, so a binary heap operation
must not terminate until both properties are in order. This outcome is simple to
achieve. (In this chapter, we use the word heap to refer to the binary heap.)
The binary heap is
the classic method
used to implement
priority queues.
21.1.1 structure property
The only structure that gives dynamic logarithmic time bounds is the tree,
so it seems natural to organize the heap's data as a tree. Because we want
 
 
Search WWH ::




Custom Search