Chapter 6

Exercise 6.1-1

Available in the latest revision of the IM.

Exercise 6.1-2

Available in the latest revision of the IM.

Exercise 6.1-3

Available in the latest revision of the IM.

Exercise 6.1-4

Available in the latest revision of the IM.

Exercise 6.1-5

Available in the latest revision of the IM.

Exercise 6.1-6

Available in the latest revision of the IM.

Exercise 6.1-7

Available in the latest revision of the IM.

Exercise 6.1-8

Available in the latest revision of the IM.

Exercise 6.2-1

Instead of presenting the solution directly, I recommend a marvelous website for visualizing algorithms called VisuAlgo. Select the option to visualize a binary heap. Choose in the bottom left corner the menu item Create(A) - O(N) and enter the following content for $A$=27,17,3,16,13,10,1,5,7,12,4,8,9,0. Press Go. You will see that nodes at indices 3 and 6 are swapped and later nodes at indices 6 and 13 are exchanged. In essence, this shows the effect of calling Max-Heapify(A,3).

Exercise 6.2-2

Available in the latest revision of the IM.

Exercise 6.2-3

The procedure Min-Heapify(A,i) differs from Max-Heapify(A,i) in the following ways:

• The variable largest should be renamed to smallest.

• At line 3, the second comparison operator should be reversed from > to <.

• At line 6, the second comparison operator should be reversed from > to <.

• Line 10 should be changed to call Min-Heapify(A,smallest).

The running times of both procedures are asymptotically the same.

Exercise 6.2-4

Available in the latest revision of the IM.

Exercise 6.2-5

Available in the latest revision of the IM.

Exercise 6.2-6

Available in the latest revision of the IM.

Exercise 6.2-7

Available in the latest revision of the IM.

Exercise 6.3-1

Follow the instructions from Exercise 6.2-1 this time entering for $A$=5,3,17,10,84,19,6,22,9 . Press Go and watch how the transformations are happening. You may also choose to monitor the process step by step.

Exercise 6.3-2

The text in the book referencing this exercise, the formulation of this exercise and the solution provided in the IM are nonsense. For any positive real $x$, it is by definition true that $\lceil x \rceil \ge 1$. What we need to prove here is that $n/2^{h+1}\ge1/2$ for $0 \le h \le \lfloor \lg n\rfloor$. We have

$$\begin{align*} \frac{n}{2^{h+1}} &\ge \frac{n}{2^{\lg n+1}} \\ &= \frac{n}{2n} \\ &= 1/2 \end{align*}$$

Exercise 6.3-3

Available in the latest revision of the IM.

Exercise 6.3-4

Available in the latest revision of the IM.

Although the proof in the IM is correct, the 4th "fact" is not true in general. It says

For nonnegative reals $a$ and $b$, we have $\lceil a \rceil b \ge \lceil ab \rceil$.

A simple counterexample is $a=1$ and $b=1/2$. In the main proof $b$ is a positive integer and $a$ is a positive integer divided by two to the power of some positive integer.

Furthermore, "facts" 1 and 5 are not trivial, thus they must be formally proven.

Simpler inductive proof

We prove the statement by induction on $h$.

The base case $h=0$ is true, since based on Exercise 6.1-8 an $n$ element heap has $\lceil n/2 \rceil$ leaves.

For the inductive step, assume that $h>0$ and denote by $m$ the number of nodes at height $h$. We know that these $m$ nodes can produce at most $2m$ children, whose quantity we can upper bound using the inductive hypothesis. Therefore,

$$2m \le \bigg\lceil \frac{n}{2^{h-1+1}} \bigg\rceil=\bigg\lceil \frac{n}{2^h} \bigg\rceil$$

which entails

$$m \le \frac{\big\lceil \frac{n}{2^h} \big\rceil}{2} \le \bigg\lceil\frac{\big\lceil \frac{n}{2^h} \big\rceil}{2}\bigg\rceil=\bigg\lceil\frac{n}{2^{h+1}}\bigg\rceil$$

We have used equation (3.5) to get rid off the inner ceil expression. This concludes the proof.

Exercise 6.4-1

Available in the latest revision of the IM.

Exercise 6.4-2

Available in the latest revision of the IM.

Exercise 6.4-3

Even if the array is sorted in increasing order, after the first step, it will be turned into a max-heap. In both cases, assuming all elements of $A$ are distinct, the extraction phase dominates, since each extraction involves swapping the root with the last element and restoring the heap property. Therefore, the asymptotic running time will remain the same $\Theta(n \lg n)$, irrespectively whether the input array is sorted in increasing or decreasing order (see also Exercise 6.4-5).

On the other hand, for special situations, like all numbers being equal, the best-case running time is $\Theta(n)$. Observe that in this case the input is sorted in both directions. Since none of the children is greater than its parent all nodes demand $\Theta(1)$ extraction time (no recursive calls will happen in Max-Heapify).

Exercise 6.4-4

We build upon Exercise 6.2-7. Suppose we have a sufficiently large array $A$ of length $n$ with $\lceil n/2 \rceil$ zeros and $\lfloor n/2 \rfloor$ ones. In step 1, this array is turned into a max-heap of height $h=\lfloor \lg n \rfloor$, with zeros as leaves. During the extraction phase, internal nodes will become roots before any leaf. Let us just focus on internal nodes at level $h-2$. Since $h-2=\Omega(h)$ and $2^{h-2}=\Omega(n)$, the total number of data movements is at least $\Omega(n) \cdot \Omega(h)=\Omega(n\lg n)$.

Exercise 6.4-5

See Theorem 1 in section 4 in the attached PDF document (downloaded from here on September 2025).

990KB

1993Heapsort.pdf

PDF

Open

Comments on the paper

The paper uses a slightly different nomenclature than the book. The number of elements is denoted by $N$ whilst $n$ denotes the number of levels, so the height is $h=n-1$.

Let us derive the average internal path length for the top $2^{n-2}$ elements, knowing that the root is one of them. At level $n-1$ we must have at least $2^{n-3}$ large keys to "pick up" those excluded at level $n$. We have

$$\begin{align*} \sum_{i=1}^{n-2} i2^{i-1} &= \frac{1}{2}\sum_{i=1}^{n-2} i2^i \\ &= \frac{1}{2}(2+(n−1−2)2^{n−1}) \\ &= 1+(n−3)2^{n−2} \\ &> (n−3)2^{n−2} \end{align*}$$

Therefore, the average internal path length is greater than $n-3$, as stated in the paper. The summation (lines 1 -> 2) is explained here.

Exercise 6.5-1

Follow the instructions from Exercise 6.2-1 this time entering for $A$=15,13,9,5,12,8,7,4,0,6,2,1. Select the ExtractMax() menu item and press 1x (Once).

Exercise 6.5-2

Available in the latest revision of the IM.

Exercise 6.5-3

See also Exercise 6.2-3.

Min-Heap-Minimum(A)
  if A.heap-size < 1
    error "heap underflow"
  return A[1]
  
Min-Heap-Extract-Min(A)
  min = Min-Heap-Minimum(A)
  A[1] = A[A.heap-size]
  A.heap-size = A.heap-size - 1
  Min-Heapify(A, 1)
  return min
  
Min-Heap-Decrease-Key(A, x, k)
  if k > x.key
    error "new key is greater than current key"
  x.key = k
  find the index i in array A where object x occurs
  while i > 1 and A[Parent(i)].key > A[i].key
    exchange A[i] with A[Parent(i)], updating the information that maps
        priority queue objects to array indices
    i = Parent(i)
    
Min-Heap-Insert(A, x, n)
  if A.heap-size == n
    error "heap overflow"
  A.heap-size = A.heap-size + 1
  k = x.key
  A[A.heap-size] = x
  map x to index heap-size in the array
  Min-Heap-Decrease-Key(A, x, k)

Exercise 6.5-4

The solution in the IM is wrong. Here is the correct version.

Max-Heap-Decrease-Key(A, x, k)
  if k > x.key
    error "new key is greater than current key"
  x.key = k
  find the index i in array A where object x occurs
  Max-Heapify(A, i)

The running time is $O(\lg n)$ plus the overhead for mapping priority queue objects to array indices.

Exercise 6.5-5

The solution in the IM is wrong. Line 5 is totally redundant. This error stems from needlessly overcomplicating the book with that satellite data story. In the 3rd edition, where only keys were stored, setting the newly allocated memory cell to $-\infin$ was mandatory to avoid the "new key is smaller than current key” error.

Exercise 6.5-6

Increasing the key of a node $x$ in a max-heap cannot violate the max-heap property between $x$ and its children, but can lead to the situation where the key of the parent of $x$ is smaller than the key of $x$. Thus, we need to traverse the path upward in a tree and float the node $x$ up, so it lands in a correct position. This task is realized by the while loop in Max-Heap-Increase-Key. Replacing the loop by a call to Max-Heapify will not work, because it can only traverse a path downward in a tree.

Exercise 6.5-7

Available in the latest revision of the IM.

Exercise 6.5-8

Available in the latest revision of the IM.

There is a bug in the IM's pseudo-code. Instead of A[i].key inside the while condition there should be x.key.

Exercise 6.5-9

Available in the latest revision of the IM.

This is a questionable objective, since both stack and queue should have a guaranteed $\Theta(1)$ performance for push/pop and enqueue/dequeue operations, respectively. Imagine using a stack where push/pop, on average, demands $\Theta(\lg n)$ time.

Exercise 6.5-10

Available in the latest revision of the IM.

Exercise 6.5-11

Available in the latest revision of the IM.

A concrete example is available here.

Problem 6-1

Available in the latest revision of the IM.

Problem 6-2

Available in the latest revision of the IM.

Problem 6-3

Available in the latest revision of the IM.

There is a bug in the IM's FLOAT procedure in part (d). The following two changes fix the issue:

• if above > left should be altered to if above > Y[i, j]

• the unconditional else should be altered to else if left > Y[i, j]

The point is that a newly inserted element may float upward and to the left until it hits a smaller or equal element.

A concrete example for part (f) is available here.