Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 27
Текст из файла (страница 27)
Thepriority-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 thekey of A[i] may violate the max-heap property, the procedure then, in a manner reminiscent ofthe insertion loop (lines 5-7) of INSERTION-SORT from Section 2.1, traverses a path fromthis node toward the root to find a proper place for the newly increased key. During thistraversal, it repeatedly compares an element to its parent, exchanging their keys andcontinuing if the element's key is larger, and terminating if the element's key is smaller, sincethe 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]2then error "new key is smaller than current key"3 A[i] ← key4 while i > 1 and A[PARENT(i)] < A[i]5do exchange A[i] ↔ A[PARENT(i)]6i ← PARENT(i)Figure 6.5 shows an example of a HEAP-INCREASE-KEY operation. The running time ofHEAP-INCREASE-KEY on an n-element heap is O(lg n), since the path traced from the nodeupdated in line 3 to the root has length O(lg n).Figure 6.5: The operation of HEAP-INCREASE-KEY.
(a) The max-heap of Figure 6.4(a)with a node whose index is i heavily shaded. (b) This node has its key increased to 15. (c)After one iteration of the while loop of lines 4-6, the node and its parent have exchanged keys,and the index i moves up to the parent. (d) The max-heap after one more iteration of the whileloop. At this point, A[PARENT(i)] ≥ A[i]. The max-heap property now holds and theprocedure terminates.The procedure MAX-HEAP-INSERT implements the INSERT operation. It takes as an inputthe key of the new element to be inserted into max-heap A. The procedure first expands themax-heap by adding to the tree a new leaf whose key is -∞. Then it calls HEAP-INCREASEKEY 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] + 12 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.Exercises 6.5-1Illustrate the operation of HEAP-EXTRACT-MAX on the heap A =0, 6, 2, 1 .15, 13, 9, 5, 12, 8, 7, 4,Exercises 6.5-2Illustrate 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.Exercises 6.5-3Write pseudocode for the procedures HEAP-MINIMUM, HEAP-EXTRACT-MIN, HEAPDECREASE-KEY, and MIN-HEAP-INSERT that implement a min-priority queue with amin-heap.Exercises 6.5-4Why do we bother setting the key of the inserted node to -∞ in line 2 of MAX-HEAPINSERT when the next thing we do is increase its key to the desired value?Exercises 6.5-5Argue 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 heapsize[A]] satisfies the max-heap property, except that there may be one violation: A[i]may be larger than A[PARENT(i)].Exercises 6.5-6Show how to implement a first-in, first-out queue with a priority queue.
Show how toimplement a stack with a priority queue. (Queues and stacks are defined in Section 10.1.)Exercises 6.5-7The operation HEAP-DELETE(A, i) deletes the item in node i from heap A. Give animplementation of HEAP-DELETE that runs in O(lg n) time for an n-element max-heap.Exercises 6.5-8Give an O(n lg k)-time algorithm to merge k sorted lists into one sorted list, where n is thetotal number of elements in all the input lists.
(Hint: Use a min-heap for k-way merging.)Problems 6-1: Building a heap using insertionThe procedure BUILD-MAX-HEAP in Section 6.3 can be implemented by repeatedly usingMAX-HEAP-INSERT to insert the elements into the heap. Consider the followingimplementation:BUILD-MAX-HEAP'(A)1 heap-size[A] ← 12 for i ← 2 to length[A]3do MAX-HEAP-INSERT(A, A[i])a. Do the procedures BUILD-MAX-HEAP and BUILD-MAX-HEAP' always create thesame heap when run on the same input array? Prove that they do, or provide acounterexample.b.
Show that in the worst case, BUILD-MAX-HEAP' requires Θ(n lg n) time to build ann-element heap.Problems 6-2: Analysis of d-ary heapsA d-ary heap is like a binary heap, but (with one possible exception) non-leaf nodes have dchildren instead of 2 children.a. How would you represent a d-ary heap in an array?b. What is the height of a d-ary heap of n elements in terms of n and d?c. Give an efficient implementation of EXTRACT-MAX in a d-ary max-heap.
Analyzeits running time in terms of d and n.d. Give an efficient implementation of INSERT in a d-ary max-heap. Analyze its runningtime in terms of d and n.e. 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 itsrunning time in terms of d and n.Problems 6-3: Young tableausAn m × n Young tableau is an m × n matrix such that the entries of each row are in sortedorder 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.a. Draw a 4×4 Young tableau containing the elements {9, 16, 3, 2, 4, 8, 5, 14, 12}.b.
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] < ∞.c. Give an algorithm to implement EXTRACT-MIN on a nonempty m × n Youngtableau that runs in O(m + n) time. Your algorithm should use a recursive subroutinethat 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.d. Show how to insert a new element into a nonfull m × n Young tableau in O(m + n)time.e. Using no other sorting method as a subroutine, show how to use an n × n Youngtableau to sort n2 numbers in O(n3) time.f. Give an O(m+n)-time algorithm to determine whether a given number is stored in agiven m × n Young tableau.Chapter notesThe heapsort algorithm was invented by Williams [316], who also described how toimplement a priority queue with a heap.
The BUILD-MAX-HEAP procedure was suggestedby Floyd [90].We use min-heaps to implement min-priority queues in Chapters 16, 23 and 24. We also givean implementation with improved time bounds for certain operations in Chapters 19 and 20.Faster implementations of priority queues are possible for integer data. A data structureinvented by van Emde Boas [301] supports the operations MINIMUM, MAXIMUM,INSERT, DELETE, SEARCH, EXTRACT-MIN, EXTRACT-MAX, PREDECESSOR, andSUCCESSOR in worst-case time O(lg lg C), subject to the restriction that the universe ofkeys is the set {1, 2, . .
. , C}. If the data are b-bit integers, and the computer memory consistsof addressable b-bit words, Fredman and Willard [99] showed how to implement MINIMUMin O(1) time and INSERT and EXTRACT-MIN intime. Thorup [299] has improvedbound to O((lg lg n)2) time. This bound uses an amount of space unbounded in n,thebut it can be implemented in linear space by using randomized hashing.An important special case of priority queues occurs when the sequence of EXTRACT-MINoperations is monotone, that is, the values returned by successive EXTRACT-MIN operationsare monotonically increasing over time.
This case arises in several important applications,such as Dijkstra's single-source shortest-paths algorithm, which is discussed in Chapter 24,and in discrete-event simulation. For Dijkstra's algorithm it is particularly important that theDECREASE-KEY operation be implemented efficiently. For the monotone case, if the dataare integers in the range 1, 2, . .
. , C, Ahuja, Melhorn, Orlin, and Tarjan [8] describe how toimplement EXTRACT-MIN and INSERT in O(lg C) amortized time (see Chapter 17 for moreon amortized analysis) and DECREASE-KEY in O(1) time, using a data structure called aradix heap. The O(lg C) bound can be improved tousing Fibonacci heaps (see Chapter20) in conjunction with radix heaps. The bound was further improved to O(lg1/3+ C) expectedtime by Cherkassky, Goldberg, and Silverstein [58], who combine the multilevel bucketingstructure of Denardo and Fox [72] with the heap of Thorup mentioned above.
Raman [256]further improved these results to obtain a bound of O(min(lg1/4+ C, lg1/3+ n)), for any fixed> 0. More detailed discussions of these results can be found in papers by Raman [256] andThorup [299].Chapter 7: QuicksortQuicksort is a sorting algorithm whose worst-case running time is Θ(n2) on an input array of nnumbers. In spite of this slow worst-case running time, quicksort is often the best practicalchoice for sorting because it is remarkably efficient on the average: its expected running timeis Θ(n lg n), and the constant factors hidden in the Θ(n lg n) notation are quite small.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
