Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 26
Текст из файла (страница 26)
Write an efficient MAX-HEAPIFY that uses an iterative control construct (a loop)instead of recursion.Exercises 6.2-6Show that the worst-case running time of MAX-HEAPIFY on a heap of size n is Ω(lg n).(Hint: For a heap with n nodes, give node values that cause MAX-HEAPIFY to be calledrecursively at every node on a path from the root down to a leaf.)6.3 Building a heapWe can use the procedure MAX-HEAPIFY in a bottom-up manner to convert an array A[1n], where n = length[A], into a max-heap. By Exercise 6.1-7, the elements in the subarrayA[(⌊n/2⌋+1) n] are all leaves of the tree, and so each is a 1-element heap to begin with.
Theprocedure BUILD-MAX-HEAP goes through the remaining nodes of the tree and runs MAXHEAPIFY on each one.BUILD-MAX-HEAP(A)1 heap-size[A] ← length[A]23for i ← ⌊length[A]/2⌋ downto 1do MAX-HEAPIFY(A, i)Figure 6.3 shows an example of the action of BUILD-MAX-HEAP.Figure 6.3: The operation of BUILD-MAX-HEAP, showing the data structure before the callto MAX-HEAPIFY in line 3 of BUILD-MAX-HEAP.
(a) A 10-element input array A and thebinary tree it represents. The figure shows that the loop index i refers to node 5 before the callMAX-HEAPIFY(A, i). (b) The data structure that results. The loop index i for the nextiteration refers to node 4. (c)-(e) Subsequent iterations of the for loop in BUILD-MAXHEAP.
Observe that whenever MAX-HEAPIFY is called on a node, the two subtrees of thatnode are both max-heaps. (f) The max-heap after BUILD-MAX-HEAP finishes.To show why BUILD-MAX-HEAP works correctly, we use the following loop invariant:•At the start of each iteration of the for loop of lines 2-3, each node i + 1, i + 2, . . . , nis the root of a max-heap.We need to show that this invariant is true prior to the first loop iteration, that each iteration ofthe loop maintains the invariant, and that the invariant provides a useful property to showcorrectness when the loop terminates.•••Initialization: Prior to the first iteration of the loop, i = ⌊n/2⌋.
Each node ⌊n/2⌋ + 1,⌊n/2⌋ + 2, . . . , n is a leaf and is thus the root of a trivial max-heap.Maintenance: To see that each iteration maintains the loop invariant, observe that thechildren of node i are numbered higher than i. By the loop invariant, therefore, theyare both roots of max-heaps. This is precisely the condition required for the call MAXHEAPIFY(A, i) to make node i a max-heap root.
Moreover, the MAX-HEAPIFY callpreserves the property that nodes i + 1, i + 2, . . . , n are all roots of max-heaps.Decrementing i in the for loop update reestablishes the loop invariant for the nextiteration.Termination: At termination, i = 0. By the loop invariant, each node 1, 2, . . .
, n isthe root of a max-heap. In particular, node 1 is.We can compute a simple upper bound on the running time of BUILD-MAX-HEAP asfollows. Each call to MAX-HEAPIFY costs O(lg n) time, and there are O(n) such calls. Thus,the running time is O(n lg n). This upper bound, though correct, is not asymptotically tight.We can derive a tighter bound by observing that the time for MAX-HEAPIFY to run at a nodevaries with the height of the node in the tree, and the heights of most nodes are small. Ourtighter analysis relies on the properties that an n-element heap has height ⌊lg n⌋ (see Exercise6.1-2) and at most ⌈n/2h+1⌉ nodes of any height h (see Exercise 6.3-3).The time required by MAX-HEAPIFY when called on a node of height h is O(h), so we canexpress the total cost of BUILD-MAX-HEAP asThe last summation can be evaluated by substituting x = 1/2 in the formula (A.8), whichyieldsThus, the running time of BUILD-MAX-HEAP can be bounded asHence, we can build a max-heap from an unordered array in linear time.We can build a min-heap by the procedure BUILD-MIN-HEAP, which is the same asBUILD-MAX-HEAP but with the call to MAX-HEAPIFY in line 3 replaced by a call toMIN-HEAPIFY (see Exercise 6.2-2).
BUILD-MIN-HEAP produces a min-heap from anunordered linear array in linear time.Exercises 6.3-1Using Figure 6.3 as a model, illustrate the operation of BUILD-MAX-HEAP on the array A =5, 3, 17, 10, 84, 19, 6, 22, 9 .Exercises 6.3-2Why do we want the loop index i in line 2 of BUILD-MAX-HEAP to decrease from⌊length[A]/2⌋ to 1 rather than increase from 1 to ⌊length[A]/2⌋?Exercises 6.3-3Show that there are at most ⌈n/2h+1⌉ nodes of height h in any n-element heap.6.4 The heapsort algorithmThe heapsort algorithm starts by using BUILD-MAX-HEAP to build a max-heap on the inputarray A[1 n], where n = length[A].
Since the maximum element of the array is stored at theroot A[1], it can be put into its correct final position by exchanging it with A[n]. If we now"discard" node n from the heap (by decrementing heap-size[A]), we observe that A[1 (n 1)] can easily be made into a max-heap. The children of the root remain max-heaps, but thenew root element may violate the max-heap property. All that is needed to restore the maxheap property, however, is one call to MAX-HEAPIFY(A, 1), which leaves a max-heap in A[1(n - 1)]. The heapsort algorithm then repeats this process for the max-heap of size n - 1down to a heap of size 2.
(See Exercise 6.4-2 for a precise loop invariant.)HEAPSORT(A)1 BUILD-MAX-HEAP(A)2 for i ← length[A] downto 23do exchange A[1] ↔ A[i]4heap-size[A] ← heap-size[A] - 15MAX-HEAPIFY(A, 1)Figure 6.4 shows an example of the operation of heapsort after the max-heap is initially built.Each max-heap is shown at the beginning of an iteration of the for loop of lines 2-5.Figure 6.4: The operation of HEAPSORT.
(a) The max-heap data structure just after it hasbeen built by BUILD-MAX-HEAP. (b)-(j) The max-heap just after each call of MAXHEAPIFY in line 5. The value of i at that time is shown. Only lightly shaded nodes remain inthe heap. (k) The resulting sorted array A.The HEAPSORT procedure takes time O(n lg n), since the call to BUILD-MAX-HEAP takestime O(n) and each of the n - 1 calls to MAX-HEAPIFY takes time O(lg n).Exercises 6.4-1Using Figure 6.4 as a model, illustrate the operation of HEAPSORT on the array A =2, 25, 7, 17, 20, 8, 4 .5, 13,Exercises 6.4-2Argue the correctness of HEAPSORT using the following loop invariant:•At the start of each iteration of the for loop of lines 2-5, the subarray A[1 i] is amax-heap containing the i smallest elements of A[1 n], and the subarray A[i + 1n] contains the n - i largest elements of A[1 n], sorted.Exercises 6.4-3What is the running time of heapsort on an array A of length n that is already sorted inincreasing order? What about decreasing order?Exercises 6.4-4Show that the worst-case running time of heapsort is Ω(n lg n).Exercises 6.4-5:Show that when all elements are distinct, the best-case running time of heapsort is Ω(n lg n).6.5 Priority queuesHeapsort is an excellent algorithm, but a good implementation of quicksort, presented inChapter 7, usually beats it in practice.
Nevertheless, the heap data structure itself hasenormous utility. In this section, we present one of the most popular applications of a heap: itsuse as an efficient priority queue. As with heaps, there are two kinds of priority queues: maxpriority queues and min-priority queues. We will focus here on how to implement maxpriority queues, which are in turn based on max-heaps; Exercise 6.5-3 asks you to write theprocedures for min-priority queues.A priority queue is a data structure for maintaining a set S of elements, each with anassociated 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 maxpriority queue keeps track of the jobs to be performed and their relative priorities. When a jobis finished or interrupted, the highest-priority job is selected from those pending usingEXTRACT-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 eventdriven simulator. The items in the queue are events to be simulated, each with an associatedtime of occurrence that serves as its key. The events must be simulated in order of their timeof occurrence, because the simulation of an event can cause other events to be simulated inthe future.
The simulation program uses EXTRACT-MIN at each step to choose the nextevent to simulate. As new events are produced, they are inserted into the min-priority queueusing INSERT. We shall see other uses for min-priority queues, highlighting theDECREASE-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 toobjects in the application. It is often necessary to determine which application objectcorresponds to a given priority-queue element, and vice-versa. When a heap is used toimplement a priority queue, therefore, we often need to store a handle to the correspondingapplication object in each heap element. The exact makeup of the handle (i.e., a pointer, aninteger, etc.) depends on the application.
Similarly, we need to store a handle to thecorresponding heap element in each application object. Here, the handle would typically be anarray 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 thearray index in the corresponding application object. Because the details of accessingapplication objects depend heavily on the application and its implementation, we shall notpursue them here, other than noting that in practice, these handles do need to be correctlymaintained.Now we discuss how to implement the operations of a max-priority queue.
The procedureHEAP-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 issimilar to the for loop body (lines 3-5) of the HEAPSORT procedure.HEAP-EXTRACT-MAX(A)1 if heap-size[A] < 12then error "heap underflow"3 max ← A[1]4 A[1] ← A[heap-size[A]]5 heap-size[A] ← heap-size[A] - 16 MAX-HEAPIFY(A, 1)7 return maxThe running time of HEAP-EXTRACT-MAX is O(lg n), since it performs only a constantamount of work on top of the O(lg n) time for MAX-HEAPIFY.The procedure HEAP-INCREASE-KEY implements the INCREASE-KEY operation.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
