6. Heapsort

Exercises

6.1-1

Available in the latest revision of the IM.

6.1-2

Available in the latest revision of the IM.

6.1-3

Available in the latest revision of the IM.

6.1-4

Available in the latest revision of the IM.

6.1-5

Available in the latest revision of the IM.

6.1-6

Available in the latest revision of the IM.

6.1-7

Available in the latest revision of the IM.

6.1-8

Available in the latest revision of the IM.

6.2-1

Instead of presenting the solution directly, I recommend a 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).

6.2-2

Available in the latest revision of the IM.

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.

6.2-4

Available in the latest revision of the IM.

6.2-5

Available in the latest revision of the IM.

6.2-6

Available in the latest revision of the IM.

6.2-7

Available in the latest revision of the IM.

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.

6.3-2

The proof 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*}$$

6.3-3

Available in the latest revision of the IM.

6.3-4

Available in the latest revision of the IM.

The proof in the IM has several issues. 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.

Consider an $n$ element heap. We want to find the number of nodes at height $h>0$. Let’s remove all the leaves from the tree, so the number of remaining nodes is $n - \lceil n/2 \rceil = \lfloor n/2 \rfloor$. Crucially, because we stripped away the bottom layer, every node that was at height $h$ in the original heap is now exactly at height $h-1$ in the new heap. Therefore, the number of nodes at height $h$ in the original $n$ element heap is exactly equal to the number of nodes at height $h-1$ in a heap of size $\lfloor n/2 \rfloor$. Therefore, we can apply the inductive hypothesis to bound the number of nodes at height $h$. This gives

$$\text{Number of nodes} \le \left\lceil \frac{\lfloor n/2 \rfloor}{2^{(h-1)+1}} \right\rceil \le \left\lceil \frac{n/2}{2^h} \right\rceil = \left\lceil \frac{n}{2^{h+1}} \right\rceil.$$

This concludes the proof.

6.4-1

Available in the latest revision of the IM.

6.4-2

Available in the latest revision of the IM.

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). In both scenarios, we are consistently taking small elements from the bottom of the tree, putting them at the root, and forcing to sink back down $O(\lg n)$ levels.

On the other hand, for special situations, like all numbers being equal, the best-case running time is $\Theta(n)$. Here, 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).

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 (internal path length) is $\Omega(n) \cdot \Omega(h)=\Omega(n\lg n)$. From another angle, data movements happen because 0s are sifting down whenever 1s are extracted at the root. For each of these first $n/4$ extractions, the 0s placed at the root must sift down past the 1s to at least level $h-2$.

★ 6.4-5

See Theorem 1 in section 4 here.

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$. The summation (lines 1 -> 2) is explained here.

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).

6.5-2

Available in the latest revision of the IM.

6.5-3

See Exercise 6.2-3 for Min-Heapify.

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)

6.5-4

The solution, at the time of this writing, 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.

6.5-5

The solution, at the time of this writing, 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 (usually filled with garbage) to $-\infin$ was mandatory to avoid the potential "new key is smaller than current key” error.

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.

6.5-7

Available in the latest revision of the IM.

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.

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.

The text of this exercise should clearly say "mimic" instead of "implement" these data structures.

6.5-10

Available in the latest revision of the IM.

6.5-11

Available in the latest revision of the IM.

A concrete example is available here.

Problems

6-1 Building a heap using insertion

Available in the latest revision of the IM.

6-2 Analysis of d-ary heaps

Available in the latest revision of the IM.

6-3 Young tableaus

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.