Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 25
Текст из файла (страница 25)
Our heap data structure is not garbage-collected storage, and whenever we referto heaps in this book, we shall mean the structure defined in this chapter..1 HeapsThe (binary) heap data structure is an array object that can be viewed as a nearly completebinary tree (see Section B.5.3), as shown in Figure 6.1. Each node of the tree corresponds toan element of the array that stores the value in the node. The tree is completely filled on alllevels except possibly the lowest, which is filled from the left up to a point.
An array A thatrepresents a heap is an object with two attributes: length[A], which is the number of elementsin the array, and heap-size[A], the number of elements in the heap stored within array A. Thatis, although A[1 length[A]] may contain valid numbers, no element past A[heap-size[A]],where heap-size[A] ≤ length[A], is an element of the heap. The root of the tree is A[1], andgiven the index i of a node, the indices of its parent PARENT(i), left child LEFT(i), and rightchild RIGHT(i) can be computed simply:PARENT(i)return ⌊i/2⌋LEFT(i)return 2iRIGHT(i)return 2i + 1Figure 6.1: A max-heap viewed as (a) a binary tree and (b) an array. The number within thecircle at each node in the tree is the value stored at that node. The number above a node is thecorresponding index in the array.
Above and below the array are lines showing parent-childrelationships; parents are always to the left of their children. The tree has height three; thenode at index 4 (with value 8) has height one.On most computers, the LEFT procedure can compute 2i in one instruction by simply shiftingthe binary representation of i left one bit position. Similarly, the RIGHT procedure canquickly compute 2i + 1 by shifting the binary representation of i left one bit position andadding in a 1 as the low-order bit.
The PARENT procedure can compute ⌊i/2⌋ by shifting iright one bit position. In a good implementation of heapsort, these three procedures are oftenimplemented as "macros" or "in-line" procedures.There are two kinds of binary heaps: max-heaps and min-heaps. In both kinds, the values inthe nodes satisfy a heap property, the specifics of which depend on the kind of heap.
In amax-heap, the max-heap property is that for every node i other than the root,A[PARENT(i)] ≥ A[i] ,that is, the value of a node is at most the value of its parent. Thus, the largest element in amax-heap is stored at the root, and the subtree rooted at a node contains values no larger thanthat contained at the node itself. A min-heap is organized in the opposite way; the min-heapproperty is that for every node i other than the root,A[PARENT(i)] ≤ A[i] .The smallest element in a min-heap is at the root.For the heapsort algorithm, we use max-heaps. Min-heaps are commonly used in priorityqueues, which we discuss in Section 6.5.
We shall be precise in specifying whether we need amax-heap or a min-heap for any particular application, and when properties apply to eithermax-heaps or min-heaps, we just use the term "heap."Viewing a heap as a tree, we define the height of a node in a heap to be the number of edgeson the longest simple downward path from the node to a leaf, and we define the height of theheap to be the height of its root.
Since a heap of n elements is based on a complete binary tree,its height is Θ(lg n) (see Exercise 6.1-2). We shall see that the basic operations on heaps runin time at most proportional to the height of the tree and thus take O(lg n) time. The remainderof this chapter presents five basic procedures and shows how they are used in a sortingalgorithm and a priority-queue data structure.••The MAX-HEAPIFY procedure, which runs in O(lg n) time, is the key to maintainingthe max-heap property.The BUILD-MAX-HEAP procedure, which runs in linear time, produces a max-heapfrom an unordered input array.••The HEAPSORT procedure, which runs in O(n lg n) time, sorts an array in place.The MAX-HEAP-INSERT, HEAP-EXTRACT-MAX, HEAP-INCREASE-KEY, andHEAP-MAXIMUM procedures, which run in O(lg n) time, allow the heap datastructure to be used as a priority queue.Exercises 6.1-1What are the minimum and maximum numbers of elements in a heap of height h?Exercises 6.1-2Show that an n-element heap has height ⌊lg n⌋.Exercises 6.1-3Show that in any subtree of a max-heap, the root of the subtree contains the largest valueoccurring anywhere in that subtree.Exercises 6.1-4Where in a max-heap might the smallest element reside, assuming that all elements aredistinct?Exercises 6.1-5Is an array that is in sorted order a min-heap?Exercises 6.1-6Is the sequenceExercises 6.1-723, 17, 14, 6, 13, 10, 1, 5, 7, 12a max-heap?Show that, with the array representation for storing an n-element heap, the leaves are thenodes indexed by ⌊n/2⌋ + 1, ⌊n/2⌋ + 2, .
. . , n.6.2 Maintaining the heap propertyMAX-HEAPIFY is an important subroutine for manipulating max-heaps. Its inputs are anarray A and an index i into the array. When MAX-HEAPIFY is called, it is assumed that thebinary trees rooted at LEFT(i) and RIGHT(i) are max-heaps, but that A[i] may be smaller thanits children, thus violating the max-heap property.
The function of MAX-HEAPIFY is to letthe value at A[i] "float down" in the max-heap so that the subtree rooted at index i becomes amax-heap.MAX-HEAPIFY(A, i)1 l ← LEFT(i)2 r ← RIGHT(i)3 if l ≤ heap-size[A] and A[l] > A[i]4then largest ← l5else largest ← i6 if r ≤ heap-size[A] and A[r] > A[largest]7then largest ← r8 if largest ≠ i9then exchange A[i] ↔ A[largest]10MAX-HEAPIFY(A, largest)Figure 6.2 illustrates the action of MAX-HEAPIFY. At each step, the largest of the elementsA[i], A[LEFT(i)], and A[RIGHT(i)] is determined, and its index is stored in largest. If A[i] islargest, then the subtree rooted at node i is a max-heap and the procedure terminates.Otherwise, one of the two children has the largest element, and A[i] is swapped withA[largest], which causes node i and its children to satisfy the max-heap property.
The nodeindexed by largest, however, now has the original value A[i], and thus the subtree rooted atlargest may violate the max-heap property. Consequently, MAX-HEAPIFY must be calledrecursively on that subtree.Figure 6.2: The action of MAX-HEAPIFY(A, 2), where heap-size[A] = 10. (a) The initialconfiguration, with A[2] at node i = 2 violating the max-heap property since it is not largerthan both children.
The max-heap property is restored for node 2 in (b) by exchanging A[2]with A[4], which destroys the max-heap property for node 4. The recursive call MAXHEAPIFY(A, 4) now has i = 4. After swapping A[4] with A[9], as shown in (c), node 4 isfixed up, and the recursive call MAX-HEAPIFY(A, 9) yields no further change to the datastructure.The running time of MAX-HEAPIFY on a subtree of size n rooted at given node i is the Θ(1)time to fix up the relationships among the elements A[i], A[LEFT(i)], and A[RIGHT(i)], plusthe time to run MAX-HEAPIFY on a subtree rooted at one of the children of node i. Thechildren's subtrees each have size at most 2n/3-the worst case occurs when the last row of thetree is exactly half full-and the running time of MAX-HEAPIFY can therefore be describedby the recurrenceT (n) ≤ T(2n/3) + Θ(1).The solution to this recurrence, by case 2 of the master theorem (Theorem 4.1), is T (n) = O(lgn).
Alternatively, we can characterize the running time of MAX-HEAPIFY on a node ofheight h as O(h).Exercises 6.2-1Using Figure 6.2 as a model, illustrate the operation of MAX-HEAPIFY(A, 3) on the array A= 27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0 .Exercises 6.2-2Starting with the procedure MAX-HEAPIFY, write pseudocode for the procedure MINHEAPIFY(A, i), which performs the corresponding manipulation on a min-heap. How doesthe running time of MIN-HEAPIFY compare to that of MAX-HEAPIFY?Exercises 6.2-3What is the effect of calling MAX-HEAPIFY(A, i) when the element A[i] is larger than itschildren?Exercises 6.2-4What is the effect of calling MAX-HEAPIFY(A, i) for i > heap-size[A]/2?Exercises 6.2-5The code for MAX-HEAPIFY is quite efficient in terms of constant factors, except possiblyfor the recursive call in line 10, which might cause some compilers to produce inefficientcode.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
