In this chapter, we introduce another sorting algorithm. Like merge sort, but unlike insertion sort, heapsort's running time is *O*(*n *lg *n*). Like insertion sort, but unlike merge sort, heapsort sorts in place: only a constant number of array elements are stored outside the input array at any time. Thus, heapsort combines the better attributes of the two sorting algorithms we have already discussed.

We note that the term "heap" was originally coined in the context of heapsort, but it has since come to refer to "garbage-collected storage," such as the programming language Lisp provides. Our heap data structure is *not* garbage-collected storage, and whenever we refer to heaps in this book, we shall mean the structure defined in this chapter.

The **(****binary****) *** heap* data structure is an array object that can be viewed as a complete binary tree (see Section 5.5.3), as shown in Figure 7.1. Each node of the tree corresponds to an element of the array that stores the value in the node. The tree is completely filled on all levels except possibly the lowest, which is filled from the left up to a point. An array

PARENT(i)

returni/2

LEFT(i)

return2i

RIGHT(i)

return2i+ 1

On most computers, the LEFT procedure can compute 2*i* in one instruction by simply shifting the binary representation of *i* left one bit position. Similarly, the RIGHT procedure can quickly compute 2*i* + 1 by shifting the binary representation of *i* left one bit position and shifting in a 1 as the low-order bit. The PARENT procedure can compute *i*/2 by shifting *i* right one bit position. In a good implementation of heapsort, these three procedures are often implemented as "macros" or "in-line" procedures.

Heaps also satisfy the * heap property*: for every node

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

We define the * height* of a node in a tree 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 tree to be the height of its root. Since a heap of

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.

What are the minimum and maximum numbers of elements in a heap of height *h*?

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?

HEAPIFY is an important subroutine for manipulating heaps. Its inputs are an array *A* and an index *i* into the array. When HEAPIFY is called, it is assumed that the binary trees rooted at LEFT(*i*) and RIGHT(*i*) are heaps, but that *A*[*i*] may be smaller than its children, thus violating the heap property (7.1). The function of HEAPIFY is to let the value at *A*[*i*] "float down" in the heap so that the subtree rooted at index *i* becomes a heap.

HEAPIFY(A,i)

1lLEFT(i)

2rRIGHT(i)

3iflheap-size[A] andA[l] >A[i]

4thenlargest l

5elselargesti

6ifrheap-size[A] andA[r] >A[largest]

7thenlargestr

8iflargesti

9thenexchangeA[i]A[largest]

10 HEAPIFY(A,largest)

T(n)T(2n/3) + (1).

Using Figure 7.2 as a model, illustrate the operation of HEAPIFY (*A,* 3) on the array *A *= 27, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0.

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?

We can use the procedure HEAPIFY in a bottom-up manner to convert an array *A*[1 . . *n*], where *n* = *length*[*A*], into a heap. Since the elements in the subarray *A*[(*n*/2 + l) . . *n*] are all leaves of the tree, each is a 1-element heap to begin with. The procedure BUILD-HEAP goes through the remaining nodes of the tree and runs HEAPIFY on each one. The order in which the nodes are processed guarantees that the subtrees rooted at children of a node *i* are heaps before HEAPIFY is run at that node.

BUILD-HEAP(A)

1heap-size[A]length[A]

2forilength[A]/2downto1

3doHEAPIFY(A, i)

Figure 7.3 shows an example of the action of BUILD-HEAP.

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.

Show that there are at most *n*/2* ^{h}*+1 nodes of height

The heapsort algorithm starts by using BUILD-HEAP to build a heap on the input array *A*[1 . . *n*], where *n* = *length*[*A*]. Since the maximum element of the array is stored at the root *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 heap. The children of the root remain heaps, but the new root element may violate the heap property (7.1). All that is needed to restore the heap property, however, is one call to HEAPIFY(*A*, 1), which leaves a heap in *A*[1 *. . *(*n -* 1)]. The heapsort algorithm then repeats this process for the heap of size *n* - 1 down to a heap of size 2.

HEAPSORT(A)

1 BUILD-HEAP(A)

2forilength[A]downto2

3doexchangeA[1]A[i]

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

5 HEAPIFY(A, 1)

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

Heapsort is an excellent algorithm, but a good implementation of quicksort, presented in Chapter 8, usually beats it in practice. Nevertheless, the heap data structure itself has enormous utility. In this section, we present one of the most popular applications of a heap: its use as an efficient priority queue.

A * priority queue* is a data structure for maintaining a set

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.

Not surprisingly, we can use a heap to implement a priority queue. The operation HEAP-MAXIMUM returns the maximum heap element in (1) time by simply returning the value *A*[1] in the heap. The HEAP-EXTRACT-MAX procedure is similar to the **for** loop body (lines 3-5) of the HEAPSORT procedure:

HEAP-EXTRACT-MAX(A)

1ifheap-size[A] < 1

2then error"heap underflow"

3maxA[1]

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

5heap-size[A]heap-size[A] - 1

6 HEAPIFY(A, 1)

7returnmax

The HEAP-INSERT procedure inserts a node into heap *A*. To do so, it first expands the heap by adding a new leaf to the tree. Then, in a manner reminiscent of the insertion loop (lines 5-7) of INSERTION-SORT from Section 1.1, it traverses a path from this leaf toward the root to find a proper place for the new element.

HEAP-INSERT(A,key)

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

2 iheap-size[A]

3whilei> 1 andA[PARENT(i)] <key

4doA[i]A[PARENT(i)]

5iPARENT(i)

6A[i]key

In summary, a heap can support any priority-queue operation on a set of size *n* in* O*(lg *n*) time.

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

Give an *O*(lg *n*)-time implementation of the procedure HEAP-INCREASE-KEY(*A, i, k*), which sets *A*[*i*] max(*A*[*i*],*k*) and updates the heap structure appropriately.

The operation HEAP-DELETE(*A, i*) deletes the item in node* i* from heap *A*. Give an implementation of HEAP-DELETE that runs in *O*(lg *n*) time for an *n*-element heap.

Give an *O(n *lg *k*)-time algorithm to merge* k *sorted lists into one sorted list, where* n* is the total number of elements in all the input lists. (*Hint*: Use a heap for *k*-way merging.)

7-1 Building a heap using insertion

The procedure BUILD-HEAP in Section 7.3 can be implemented by repeatedly using HEAP-INSERT to insert the elements into the heap. Consider the following implementation:

BUILD-HEAP'(A)

1heap-size[A] 1

2fori2tolength[A]

3doHEAP-INSERT(A, A[i])

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

A **d-ary*** heap* is like a binary heap, but instead of 2 children, nodes have

**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. Analyze its running time in terms of *d* and *n*.

**d***. *Give an efficient implementation of INSERT. Analyze its running time in terms of *d* and *n*.