Heap Sort
Quick Notes
- Heapsort’s running time is O(n lg n).
- Like insertion sort, but unlike merge sort, heapsort sorts in place.
- Heapsort also introduces another algorithm design technique: using a data structure, in this case one we call a “heap,” to manage information.
Heaps
The (binary) heap data structure is an array object that we can view as a
nearly complete binary tree. Each
node of the tree corresponds to an element of the array. The tree is completely filled on all levels except possibly the lowest, which is filled from the
left up to a point. An array A that represents a heap is an object with two attributes: A.length, which (as usual) gives the number of elements in the array, and
A.heap-size, which represents how many elements in the heap are stored within
array A. That is, although A[1 . . A.length] may contain numbers, only the elements in A[1 . . A.heap-size], where 0 ≤ A.heap-size ≤ A.length, are valid elements of the heap. The root of the tree is A[1], and given the index i of a node, we
can easily compute the indices of its parent, left child, and right child.
PARENT
return [i/2]
LEFT
return 2i
RIGHT
return 2i + 1
On most computers, the LEFT procedure can compute 2i in one instruction by simply shifting the binary representation of i left by one bit position. Similarly, the RIGHT procedure can quickly compute 2i +1 by shifting the binary representation of i left by one bit position and then adding in a 1 as the low-order bit. The PARENT procedure can compute [i/2] by shifting i right one bit position. Good implementations of heapsort often implement these procedures as “macros” or “inline” procedures.
There are two kinds of binary heaps: max-heaps and min-heaps. In both kinds, the values in the nodes satisfy a heap property, the specifics of which depend on the kind of heap. In a max-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 a max-heap is stored at the root, and the subtree rooted at a node contains values no larger than that contained at the node itself. A min-heap is organized in the opposite way; the min-heap property 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 commonly implement priority queues. We shall be precise in specifying whether we need a max-heap or a min-heap for any particular application, and when properties apply to either max-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 edges on the longest simple downward path from the node to a leaf, and we define the height of the heap 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). We shall see that the basic operations on heaps run in time at most proportional to the height of the tree and thus take O(lg n) time.
Figure illustrates the action of MAX-HEAPIFY. At each step, the largest of the elements A[i], A[LEFT(i)], and A[RIGHT(i)] is determined, and its index is stored in largest. If A[i] is largest, then the subtree rooted at node i is already a max-heap and the procedure terminates. Otherwise, one of the two children has the largest element, and A[i] is swapped with A[largest], which causes node i and its children to satisfy the max-heap property. The node indexed by largest, however, now has the original value A[i], and thus the subtree rooted at largest might violate the max-heap property. Consequently, we call MAX-HEAPIFY recursively on that subtree.
The running time of MAX-HEAPIFY on a subtree of size n rooted at a given
node i is the θ(1) time to fix up the relationships among the elements A[i],
A[LEFT(i)], and A[RIGHT(i)], plus the time to run MAX-HEAPIFY on a subtree
rooted at one of the children of node i (assuming that the recursive call occurs).
The children’s subtrees each have size at most 2n/3—the worst case occurs when
the bottom level of the tree is exactly half full—and therefore we can describe the
running time of MAX-HEAPIFY by the recurrence
T(n) ≤ T(2n/3) + θ(1) .
The solution to this recurrence, by case 2 of the master theorem (Theorem 4.1), is T (n) = O(lg n). Alternatively, we can characterize the running time of MAXHEAPIFY on a node of height h as O(h).
To show why BUILD-MAX-HEAP works correctly, we use the following loop invariant:
 |
| A max-heap viewed as (a) a binary tree and (b) an array. The number within the circle at each node in the tree is the value stored at that node. The number above a node is the corresponding index in the array. Above and below the array are lines showing parent-child relationships; parents are always to the left of their children. The tree has height three; the node at index 4 (with value 8) has height one. |
return [i/2]
LEFT
return 2i
RIGHT
return 2i + 1
On most computers, the LEFT procedure can compute 2i in one instruction by simply shifting the binary representation of i left by one bit position. Similarly, the RIGHT procedure can quickly compute 2i +1 by shifting the binary representation of i left by one bit position and then adding in a 1 as the low-order bit. The PARENT procedure can compute [i/2] by shifting i right one bit position. Good implementations of heapsort often implement these procedures as “macros” or “inline” procedures.
There are two kinds of binary heaps: max-heaps and min-heaps. In both kinds, the values in the nodes satisfy a heap property, the specifics of which depend on the kind of heap. In a max-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 a max-heap is stored at the root, and the subtree rooted at a node contains values no larger than that contained at the node itself. A min-heap is organized in the opposite way; the min-heap property 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 commonly implement priority queues. We shall be precise in specifying whether we need a max-heap or a min-heap for any particular application, and when properties apply to either max-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 edges on the longest simple downward path from the node to a leaf, and we define the height of the heap 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). We shall see that the basic operations on heaps run in time at most proportional to the height of the tree and thus take O(lg n) time.
- The MAX-HEAPIFY procedure, which runs in O(lg n) time, is the key to maintaining the max-heap property.
- The BUILD-MAX-HEAP procedure, which runs in linear time, produces a maxheap from 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, and HEAP-MAXIMUM procedures, which run in O(lg n) time, allow the heap data structure to implement a priority queue.
Maintaining the heap property
In order to maintain the max-heap property, we call the procedure MAX-HEAPIFY. Its inputs are an array A and an index i into the array. When it is called, MAXHEAPIFY assumes that the binary trees rooted at LEFT(i) and RIGHT(i) are maxheaps, but that A[i] might be smaller than its children, thus violating the max-heap property. MAX-HEAPIFY lets the value at A[i] “float down” in the max-heap so that the subtree rooted at index i obeys the max-heap property.
Figure illustrates the action of MAX-HEAPIFY. At each step, the largest of the elements A[i], A[LEFT(i)], and A[RIGHT(i)] is determined, and its index is stored in largest. If A[i] is largest, then the subtree rooted at node i is already a max-heap and the procedure terminates. Otherwise, one of the two children has the largest element, and A[i] is swapped with A[largest], which causes node i and its children to satisfy the max-heap property. The node indexed by largest, however, now has the original value A[i], and thus the subtree rooted at largest might violate the max-heap property. Consequently, we call MAX-HEAPIFY recursively on that subtree.
 |
| The action of MAX-HEAPIFY(A, 2), where A.heap-size = 10. (a) The initial configuration, with A[2] at node i = 2 violating the max-heap property since it is not larger than 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 MAX-HEAPIFY(A, 4) now has i = 4. After swapping A[4] with A[9], as shown in (c), node 4 is fixed up, and the recursive call MAX-HEAPIFY(A, 9) yields no further change to the data structure. |
T(n) ≤ T(2n/3) + θ(1) .
The solution to this recurrence, by case 2 of the master theorem (Theorem 4.1), is T (n) = O(lg n). Alternatively, we can characterize the running time of MAXHEAPIFY on a node of height h as O(h).
Building a heap
We can use the procedure MAX-HEAPIFY in a bottom-up manner to convert an
array A[1 . . n], where n = A.length, into a max-heap. The
elements in the subarray A[(n/2 + 1) . . n] are all leaves of the tree, and so each is a 1-element heap to begin with. The procedure BUILD-MAX-HEAP goes through
the remaining nodes of the tree and runs MAX-HEAPIFY on each one.
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, . . . , n is the root of a max-heap.
We need to show that this invariant is true prior to the first loop iteration, that each
iteration of the loop maintains the invariant, and that the invariant provides a useful
property to show correctness 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 the children of node i are numbered higher than i. By the loop invariant, therefore, they are both roots of max-heaps. This is precisely the condition required for the call MAX-HEAPIFY(A, i) to make node i a max-heap root. Moreover, the MAX-HEAPIFY call preserves 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 next iteration.
- Termination: At termination, i = 0. By the loop invariant, each node 1, 2, . . . , n is the root of a max-heap. In particular, node 1 is.
We can compute a simple upper bound on the running time of BUILD-MAXHEAP as follows. Each call to MAX-HEAPIFY costs O(lg n) time, and BUILDMAX-HEAP makes 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 node varies with the height of the node in the tree, and the heights of most nodes are small. Our tighter analysis relies on the properties that an n-element heap has height [lg n] and at most [n/2h+1] nodes of any height h. The time required by MAX-HEAPIFY when called on a node of height h is O(h), and so we can express the total cost of BUILD-MAX-HEAP as being bounded from above by
Hence, 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 as BUILD-MAX-HEAP but with the call to MAX-HEAPIFY in line 3 replaced by a call to MIN-HEAPIFY. BUILD-MIN-HEAP produces a min-heap from an unordered linear array in linear time.
We can derive a tighter bound by observing that the time for MAX-HEAPIFY to run at a node varies with the height of the node in the tree, and the heights of most nodes are small. Our tighter analysis relies on the properties that an n-element heap has height [lg n] and at most [n/2h+1] nodes of any height h. The time required by MAX-HEAPIFY when called on a node of height h is O(h), and so we can express the total cost of BUILD-MAX-HEAP as being bounded from above by
Hence, 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 as BUILD-MAX-HEAP but with the call to MAX-HEAPIFY in line 3 replaced by a call to MIN-HEAPIFY. BUILD-MIN-HEAP produces a min-heap from an unordered linear array in linear time.
The heapsort algorithm
The heapsort algorithm starts by using BUILD-MAX-HEAP to build a max-heap
on the input array A[1 . . n], where n = A.length. Since the maximum element
of the array is stored at the root A[1], we can put it into its correct final position by exchanging it with A[n]. If we now discard node n from the heap—and we
can do so by simply decrementing A.heap-size—we observe that the children of
the root remain max-heaps, but the new root element might violate the max-heap
property. All we need to do to restore the max-heap property, however, is call
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 - 1 down to a heap
of size 2.
Figure shows an example of the operation of HEAPSORT after line 1 has built
the initial max-heap. The figure shows the max-heap before the first iteration of
the for loop of lines 2–5 and after each iteration.
The HEAPSORT procedure takes time O(n lg n), since the call to BUILD-MAXHEAP takes time O(n) and each of the n - 1 calls to MAX-HEAPIFY takes
time O(lg n).
Comments
Post a Comment