# 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](https://visualgo.net/). Select the [option to visualize a binary heap](https://visualgo.net/en/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](#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](#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](#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](#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](https://sedgewick.io/wp-content/themes/sedgewick/papers/1993Heapsort.pdf) on September 2025). {% file src="" %} ### 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](https://math.stackexchange.com/a/250747/753413). ## Exercise 6.5-1 Follow the instructions from [Exercise 6.2-1](#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](#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.** {% hint style="danger" %} There is a bug in the IM's pseudo-code. Instead of `A[i].key` inside the `while` condition there should be `x.key`. {% endhint %} ## Exercise 6.5-9 **Available in the latest revision of the IM.** {% hint style="warning" %} 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. {% endhint %} ## Exercise 6.5-10 **Available in the latest revision of the IM.** ## Exercise 6.5-11 **Available in the latest revision of the IM.** {% hint style="success" %} A concrete example is available [here](https://leetcode.com/problems/merge-k-sorted-lists/). {% endhint %} ## 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.** {% hint style="danger" %} 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. {% endhint %} {% hint style="success" %} A concrete example for part (f) is available [here](https://leetcode.com/problems/search-a-2d-matrix-ii/). {% endhint %}