|
|
< Day Day Up > |
|
This chapter and Chapter 20 present data structures known as mergeable heaps, which support the following five operations.
MAKE-HEAP() creates and returns a new heap containing no elements.
INSERT(H, x) inserts node x, whose key field has already been filled in, into heap H.
MINIMUM(H) returns a pointer to the node in heap H whose key is minimum.
EXTRACT-MIN(H) deletes the node from heap H whose key is minimum, returning a pointer to the node.
UNION(H1, H2) creates and returns a new heap that contains all the nodes of heaps H1 and H2. Heaps H1 and H2 are "destroyed" by this operation.
In addition, the data structures in these chapters also support the following two operations.
DECREASE-KEY(H, x, k) assigns to node x within heap H the new key value k, which is assumed to be no greater than its current key value.[1]
DELETE(H, x) deletes node x from heap H.
As the table in Figure 19.1 shows, if we don't need the UNION operation, ordinary binary heaps, as used in heapsort (Chapter 6), work well. Operations other than UNION run in worst-case time O(lg n) (or better) on a binary heap. If the UNION operation must be supported, however, binary heaps perform poorly. By concatenating the two arrays that hold the binary heaps to be merged and then running MIN-HEAPIFY (see Exercise 6.2-2), the UNION operation takes Θ(n) time in the worst case.
 |
|
Procedure |
Binary heap (worst-case) |
Binomial heap (worst-case) |
Fibonacci heap (amortized) |
|---|---|---|---|
|
|
|||
|
MAKE-HEAP |
Θ(1) |
Θ(1) |
Θ(1) |
|
INSERT |
Θ(lg n) |
O(lg n) |
Θ(1) |
|
MINIMUM |
Θ(1) |
O(lg n) |
Θ(1) |
|
EXTRACT-MIN |
Θ(lg n) |
Θ(lg n) |
O(lg n) |
|
UNION |
Θ(n) |
O(lg n) |
Θ(1) |
|
DECREASE-KEY |
Θ(lg n) |
Θ(lg n) |
Θ(1) |
|
DELETE |
Θ(lg n) |
Θ(lg n) |
O(lg n) |
|
In this chapter, we examine "binomial heaps," whose worst-case time bounds are also shown in Figure 19.1. In particular, the UNION operation takes only O(lg n) time to merge two binomial heaps with a total of n elements.
In Chapter 20, we shall explore Fibonacci heaps, which have even better time bounds for some operations. Note, however, that the running times for Fibonacci heaps in Figure 19.1 are amortized time bounds, not worst-case per-operation time bounds.
This chapter ignores issues of allocating nodes prior to insertion and freeing nodes following deletion. We assume that the code that calls the heap procedures deals with these details.
Binary heaps, binomial heaps, and Fibonacci heaps are all inefficient in their support of the operation SEARCH; it can take a while to find a node with a given key. For this reason, operations such as DECREASE-KEY and DELETE that refer to a given node require a pointer to that node as part of their input. As in our discussion of priority queues in Section 6.5, when we use a mergeable heap in an application, we often store a handle to the corresponding application object in each mergeable-heap element, as well as a handle to corresponding mergeable-heap element in each application object. The exact nature of these handles depends on the application and its implementation.
Section 19.1 defines binomial heaps after first defining their constituent binomial trees. It also introduces a particular representation of binomial heaps. Section 19.2 shows how we can implement operations on binomial heaps in the time bounds given in Figure 19.1.
|
|
< Day Day Up > |
|