# CHAPTER 7: HEAPSORT

Heapsort also introduces another algorithm design technique: the use of a data structure, in this case one we call a "heap," to manage information during the execution of the algorithm. Not only is the heap data structure useful for heapsort, it also makes an efficient priority queue. The heap data structure will reappear in algorithms in later chapters.

# 7.1 Heaps

#### Figure 7.1 A 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 next to a node is the corresponding index in the array.

`PARENT(i)`

`return i/2`

`LEFT(i)`

`return 2i`

`RIGHT(i)`

`return 2i + 1`

`A[PARENT(i)]  A[i],`

#### (7.1)

that is, the value of a node is at most the value of its parent. Thus, the largest element in a heap is stored at the root, and the subtrees rooted at a node contain smaller values than does the node itself.

The HEAPIFY procedure, which runs in O(lg n) time, is the key to maintaining the heap property (7.1).

The BUILD-HEAP procedure, which runs in linear time, produces a heap from an unordered input array.

The HEAPSORT procedure, which runs in O(n lg n) time, sorts an array in place.

The EXTRACT-MAX and INSERT procedures, which run in O(1g n) time, allow the heap data structure to be used as a priority queue.

## Exercises

Show that an n-element heap has height lg n.

Show that the largest element in a subtree of a heap is at the root of the subtree.

Where in a heap might the smallest element reside?

Is an array that is in reverse sorted order a heap?

Is the sequence 23, 17, 14, 6, 13, 10, 1, 5, 7, 12 a heap?

# 7.2 Maintaining the heap property

#### Figure 7.2 The action of HEAPIFY(A, 2), where heap-size[A] = 10. (a) The initial configuration of the heap, with A[2] at node i = 2 violating the heap property since it is not larger than both children. The heap property is restored for node 2 in (b) by exchanging A[2] with A[4], which destroys the heap property for node 4. The recursive call HEAPIFY(A, 4) now sets i = 4. After swapping A[4] with A[9], as shown in (c), node 4 is fixed up, and the recursive call HEAPIFY(A, 9) yields no further change to the data structure.

`HEAPIFY(A, i)`

`1 l  LEFT(i)`

`2 r  RIGHT(i)`

`3 if l  heap-size[A] and A[l] > A[i]`

`4     then largest  l`

`5     else largest  i`

`6 if r  heap-size[A] and A[r] > A[largest]`

`7     then largest  r`

`8 if largest  i`

`9     then exchange A[i]  A[largest]`

`10          HEAPIFY(A,largest)`

Figure 7.2 illustrates the action of 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 a 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 heap property. The node largest, however, now has the original value A[i], and thus the subtree rooted at largest may violate the heap property. Consequently, HEAPIFY must be called recursively on that subtree.

The running time of 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)], plus the time to run HEAPIFY on a subtree rooted at one of the children of node i. The children's subtrees each have size at most 2n/3--the worst case occurs when the last row of the tree is exactly half full--and the running time of HEAPIFY can therefore be described 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 HEAPIFY on a node of height h as O(h).

## Exercises

What is the effect of calling HEAPIFY(A, i) when the element A[i] is larger than its children?

What is the effect of calling HEAPIFY (A, i) for i > heap-size [A]/2?

The code for HEAPIFY is quite efficient in terms of constant factors, except possibly for the recursive call in line 10, which might cause some compilers to produce inefficient code. Write an efficient HEAPIFY that uses an iterative control construct (a loop) instead of recursion.

Show that the worst-case running time of HEAPIFY on a heap of size n is (lg n). (Hint: For a heap with n nodes, give node values that cause HEAPIFY to be called recursively at every node on a path from the root down to a leaf.)

# 7.3 Building a heap

`BUILD-HEAP(A)`

`1  heap-size[A]  length[A]`

`2  for i  length[A]/2downto 1`

`3        do HEAPIFY(A, i)`

We can compute a simple upper bound on the running time of BUILD-HEAP as follows. Each call to HEAPIFY costs O(lg n) time, and there are O(n) such calls. Thus, the running time is at most 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 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 property that in an n-element heap there are at most n/2h+1 nodes of height h (see Exercise 7.3-3).

The time required by HEAPIFY when called on a node of height h is O(h), so we can express the total cost of BUILD-HEAP as

#### (7.2)

The last summation can be evaluated by substituting x = 1/2 in the formula (3.6), which yields

Thus, the running time of BUILD-HEAP can be bounded as

Hence, we can build a heap from an unordered array in linear time.

## Exercises

Using Figure 7.3 as a model, illustrate the operation of BUILD-HEAP on the array A = 5, 3, 17, 10, 84, 19, 6, 22, 9.

Why do we want the loop index i in line 2 of BUILD-HEAP to decrease from length[A]/2 to 1 rather than increase from 1 to length[A]/2?

# 7.4 The heapsort algorithm

`HEAPSORT(A)`

`1  BUILD-HEAP(A)`

`2  for i  length[A] downto 2`

`3        do exchange A[1]  A[i]`

`4           heap-size[A]  heap-size[A] -1`

`5           HEAPIFY(A, 1)`

Figure 7.4 shows an example of the operation of heapsort after the heap is initially built. Each heap is shown at the beginning of an iteration of the for loop in line 2.

The HEAPSORT procedure takes time O(n lg n), since the call to BUILD-HEAP takes time O(n) and each of the n - 1 calls to HEAPIFY takes time O(lg n).

## Exercises

Using Figure 7.4 as a model, illustrate the operation of HEAPSORT on the array A = 5, 13, 2, 25, 7, 17, 20, 8, 4.

What is the running time of heapsort on an array A of length n that is already sorted in increasing order? What about decreasing order?

Show that the running time of heapsort is (n lg n).

# 7.5 Priority queues

One application of priority queues is to schedule jobs on a shared computer. The 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.

A priority queue can also 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. For this application, it is natural to reverse the linear order of the priority queue and support the operations MINIMUM and EXTRACT-MIN instead of MAXIMUM and EXTRACT-MAX. 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 priority queue using INSERT.

`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  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 HEAPIFY.

`HEAP-INSERT(A,key)`

`1  heap-size[A]  heap-size[A] + 1`

`2  i  heap-size[A]`

`3  while i > 1 and A[PARENT(i)] < key`

`4      do A[i]  A[PARENT(i)]`

`5         i  PARENT(i)`

`6  A[i]  key`

Figure 7.5 shows an example of a HEAP-INSERT operation. The running time of HEAP-INSERT on an n-element heap is O(lg n), since the path traced from the new leaf to the root has length 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

Using Figure 7.5 as a model, illustrate the operation of HEAP-INSERT(A, 3) on the heap A = 15,13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1.

Illustrate the operation of HEAP-EXTRACT-MAX on the heap A = 15, 13, 9, 5, 12, 8, 7, 4, 0, 6, 2, 1.

#### Figure 7.5 The operation of HEAP-INSERT. (a) The heap of Figure 7.4(a) before we insert a node with key 15. (b) A new leaf is added to the tree. (c) Values on the path from the new leaf to the root are copied down until a place for the key 15 is found. (d) The key 15 is inserted.

Show how to implement a first-in, first-out queue with a priority queue. Show how to implement a stack with a priority queue. (FIFO's and stacks are defined in Section 11.1.)

# Problems

`BUILD-HEAP'(A )`

`1  heap-size[A]  1`

`2  for i  2 to length[A]`

`3        do HEAP-INSERT(A, A[i])`

a. Do the procedures BUILD-HEAP and BUILD-HEAP' always create the same heap when run on the same input array? Prove that they do, or provide a counterexample.

b. Show that in the worst case, BUILD-HEAP' requires (n lg n) time to build an n-element heap.

a. How would you represent a d-ary heap in an array?

e. Give an efficient implementation of HEAP-INCREASE-KEY(A, i, k), which sets A[i] max(A[i], k) and updates the heap structure appropriately. Analyze its running time in terms of d and n.

# Chapter notes

The heapsort algorithm was invented by Williams [202], who also described how to implement a priority queue with a heap. The BUILD-HEAP procedure was suggested by Floyd [69].