|
|
< Day Day Up > |
|
Heapsort is an excellent algorithm, but a good implementation of quicksort, presented in Chapter 7, usually beats it in practice. Nevertheless, the heap data structure itself has enormous utility. In this section, we present one of the most popular applications of a heap: its use as an efficient priority queue. As with heaps, there are two kinds of priority queues: max-priority queues and min-priority queues. We will focus here on how to implement max-priority queues, which are in turn based on max-heaps; Exercise 6.5-3 asks you to write the procedures for min-priority queues.
A priority queue is a data structure for maintaining a set S of elements, each with an associated value called a key. A max-priority queue supports the following operations.
INSERT(S, x) inserts the element x into the set S. This operation could be written as S ← S ∪ {x}.
MAXIMUM(S) returns the element of S with the largest key.
EXTRACT-MAX(S) removes and returns the element of S with the largest key.
INCREASE-KEY(S, x, k) increases the value of element x's key to the new value k, which is assumed to be at least as large as x's current key value.
One application of max-priority queues is to schedule jobs on a shared computer. The max-priority queue keeps track of the jobs to be performed and their relative priorities. When a job is finished or interrupted, the highest-priority job is selected from those pending using EXTRACT-MAX. A new job can be added to the queue at any time using INSERT.
Alternatively, a min-priority queue supports the operations INSERT, MINIMUM, EXTRACT-MIN, and DECREASE-KEY. A min-priority queue can be used in an event-driven simulator. The items in the queue are events to be simulated, each with an associated time of occurrence that serves as its key. The events must be simulated in order of their time of occurrence, because the simulation of an event can cause other events to be simulated in the future. The simulation program uses EXTRACT-MIN at each step to choose the next event to simulate. As new events are produced, they are inserted into the min-priority queue using INSERT. We shall see other uses for min-priority queues, highlighting the DECREASE-KEY operation, in Chapters 23 and 24.
Not surprisingly, we can use a heap to implement a priority queue. In a given application, such as job scheduling or event-driven simulation, elements of a priority queue correspond to objects in the application. It is often necessary to determine which application object corresponds to a given priority-queue element, and vice-versa. When a heap is used to implement a priority queue, therefore, we often need to store a handle to the corresponding application object in each heap element. The exact makeup of the handle (i.e., a pointer, an integer, etc.) depends on the application. Similarly, we need to store a handle to the corresponding heap element in each application object. Here, the handle would typically be an array index. Because heap elements change locations within the array during heap operations, an actual implementation, upon relocating a heap element, would also have to update the array index in the corresponding application object. Because the details of accessing application objects depend heavily on the application and its implementation, we shall not pursue them here, other than noting that in practice, these handles do need to be correctly maintained.
Now we discuss how to implement the operations of a max-priority queue. The procedure HEAP-MAXIMUM implements the MAXIMUM operation in Θ(1) time.
HEAP-MAXIMUM(A) 1 return A[1]
The procedure HEAP-EXTRACT-MAX implements the EXTRACT-MAX operation. It is similar to the for loop body (lines 3-5) of the HEAPSORT procedure.
HEAP-EXTRACT-MAX(A) 1 if heap-size[A] < 1 2 then error "heap underflow" 3 max ← A[1] 4 A[1] ← A[heap-size[A]] 5 heap-size[A] ← heap-size[A] - 1 6 MAX-HEAPIFY(A, 1) 7 return max
The running time of HEAP-EXTRACT-MAX is O(lg n), since it performs only a constant amount of work on top of the O(lg n) time for MAX-HEAPIFY.
The procedure HEAP-INCREASE-KEY implements the INCREASE-KEY operation. The priority-queue element whose key is to be increased is identified by an index i into the array. The procedure first updates the key of element A[i] to its new value. Because increasing the key of A[i] may violate the max-heap property, the procedure then, in a manner reminiscent of the insertion loop (lines 5-7) of INSERTION-SORT from Section 2.1, traverses a path from this node toward the root to find a proper place for the newly increased key. During this traversal, it repeatedly compares an element to its parent, exchanging their keys and continuing if the element's key is larger, and terminating if the element's key is smaller, since the max-heap property now holds. (See Exercise 6.5-5 for a precise loop invariant.)
HEAP-INCREASE-KEY(A, i, key) 1 if key < A[i] 2 then error "new key is smaller than current key" 3 A[i] ← key 4 while i > 1 and A[PARENT(i)] < A[i] 5 do exchange A[i] ↔ A[PARENT(i)] 6 i ← PARENT(i)
Figure 6.5 shows an example of a HEAP-INCREASE-KEY operation. The running time of HEAP-INCREASE-KEY on an n-element heap is O(lg n), since the path traced from the node updated in line 3 to the root has length O(lg n).
The procedure MAX-HEAP-INSERT implements the INSERT operation. It takes as an input the key of the new element to be inserted into max-heap A. The procedure first expands the max-heap by adding to the tree a new leaf whose key is -∞. Then it calls HEAP-INCREASE-KEY to set the key of this new node to its correct value and maintain the max-heap property.
MAX-HEAP-INSERT(A, key) 1 heap-size[A] ← heap-size[A] + 1 2 A[heap-size[A]] ← -∞ 3 HEAP-INCREASE-KEY(A, heap-size[A], key)
The running time of MAX-HEAP-INSERT on an n-element heap is O(lg n).
In summary, a heap can support any priority-queue operation on a set of size n in O(lg n) time.
 |
Illustrate the operation of HEAP-EXTRACT-MAX on the heap A = 〈15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1〉.
|
|
Illustrate the operation of MAX-HEAP-INSERT(A, 10) on the heap A = 〈15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1〉. Use the heap of Figure 6.5 as a model for the HEAP-INCREASE-KEY call.
|
|
Write pseudocode for the procedures HEAP-MINIMUM, HEAP-EXTRACT-MIN, HEAP-DECREASE-KEY, and MIN-HEAP-INSERT that implement a min-priority queue with a min-heap.
|
|
Why do we bother setting the key of the inserted node to -∞ in line 2 of MAX-HEAP-INSERT when the next thing we do is increase its key to the desired value?
|
|
Argue the correctness of HEAP-INCREASE-KEY using the following loop invariant:
At the start of each iteration of the while loop of lines 4-6, the array A[1 ‥ heap-size[A]] satisfies the max-heap property, except that there may be one violation: A[i] may be larger than A[PARENT(i)].
|
|
Show how to implement a first-in, first-out queue with a priority queue. Show how to implement a stack with a priority queue. (Queues and stacks are defined in Section 10.1.)
|
|
The operation HEAP-DELETE(A, i) deletes the item in node i from heap A. Give an implementation of HEAP-DELETE that runs in O(lg n) time for an n-element max-heap.
|
|
Give an O(n lg k)-time algorithm to merge k sorted lists into one sorted list, where n is the total number of elements in all the input lists. (Hint: Use a min-heap for k-way merging.)
|
|
The procedure BUILD-MAX-HEAP in Section 6.3 can be implemented by repeatedly using MAX-HEAP-INSERT to insert the elements into the heap. Consider the following implementation:
BUILD-MAX-HEAP'(A) 1 heap-size[A] ← 1 2 for i ← 2 to length[A] 3 do MAX-HEAP-INSERT(A, A[i])
Do the procedures BUILD-MAX-HEAP and BUILD-MAX-HEAP' always create the same heap when run on the same input array? Prove that they do, or provide a counterexample.
Show that in the worst case, BUILD-MAX-HEAP' requires Θ(n lg n) time to build an n-element heap.
|
|
A d-ary heap is like a binary heap, but (with one possible exception) non-leaf nodes have d children instead of 2 children.
How would you represent a d-ary heap in an array?
What is the height of a d-ary heap of n elements in terms of n and d?
Give an efficient implementation of EXTRACT-MAX in a d-ary max-heap. Analyze its running time in terms of d and n.
Give an efficient implementation of INSERT in a d-ary max-heap. Analyze its running time in terms of d and n.
Give an efficient implementation of INCREASE-KEY(A, i, k), which first sets A[i] ← max(A[i], k) and then updates the d-ary max-heap structure appropriately. Analyze its running time in terms of d and n.
|
|
An m × n Young tableau is an m × n matrix such that the entries of each row are in sorted order from left to right and the entries of each column are in sorted order from top to bottom. Some of the entries of a Young tableau may be ∞, which we treat as nonexistent elements. Thus, a Young tableau can be used to hold r ≤ mn finite numbers.
Draw a 4×4 Young tableau containing the elements {9, 16, 3, 2, 4, 8, 5, 14, 12}.
Argue that an m × n Young tableau Y is empty if Y[1, 1] = ∞. Argue that Y is full (contains mn elements) if Y[m, n] < ∞.
Give an algorithm to implement EXTRACT-MIN on a nonempty m × n Young tableau that runs in O(m + n) time. Your algorithm should use a recursive subroutine that solves an m × n problem by recursively solving either an (m - 1) × n or an m × (n - 1) subproblem. (Hint: Think about MAX-HEAPIFY.) Define T(p), where p = m + n, to be the maximum running time of EXTRACT-MIN on any m × n Young tableau. Give and solve a recurrence for T(p) that yields the O(m + n) time bound.
Show how to insert a new element into a nonfull m × n Young tableau in O(m + n) time.
Using no other sorting method as a subroutine, show how to use an n × n Young tableau to sort n2 numbers in O(n3) time.
Give an O(m+n)-time algorithm to determine whether a given number is stored in a given m × n Young tableau.
|
|
|
< Day Day Up > |
|