[Algo] Problem 6

Problem 6-1 Building a heap using insertion
The procdure BUILD-MAX-HEAP in section 6.3 can be implemented by repeatedly using MAX-HEAP-INSERT to insert the elements into the heap. Consider the following implementation:


a. Do the procedure BUILD-MAX-HEAP and BUILD-MAX-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-MAX-HEAP' requires $\Theta(n \lg n)$ time to build an n-element heap.

Solution:
a. Given an array A = <2, 3, 1, 4, 5>, procedure BUILD-MAX-HEAP will give the output A = <5, 4, 1, 2, 3> and procedure BUILD-MAX-HEAP' will give the output A = <5, 4, 1, 3, 2>

b.Obviously, the upper bound is $O(n \lg n)$ due to calling procedure MAX-HEAP-INSERT (n-1) times. For the lower bound, consider the worst case which is input in increasing order. Each inserted item goes along a path from leaf to root. Since the depth is $\lfloor \lg i \rfloor$, the total time is:
$\sum_{i = 1}^{n-1} \Theta(\lfloor \lg i \rfloor) \geq \sum_{i = \lceil n/2 \rceil}^{n-1} \Theta(\lfloor \lg \lceil n/2\rceil \rfloor) \geq \sum_{i = \lceil n/2 \rceil}^{n-1} \Theta(\lfloor \lg(n/2) \rfloor)$
$ = \sum_{i = \lceil n/2 \rceil}^{n-1} \Theta(\lfloor \lg(n) - 1 \rfloor) \geq n/2 \cdot \Theta(\lg n) = \Omega(n \lg n)$
Thus, BUILD-MAX-HEAP' requires $\Theta(n \lg n)$ time to build a n-element heap.


Problem 6-2 Analysis of d-ary heaps
A d-ary heap is like a binary heap, but (with one possible exception) non-leaf nodes have d children instead of 2 children.
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 in a d-ary max-heap. Analyze its running time in terms of d and n.
d. Give an efficient implementation of INSERT in a d-ary max-heap. Analyze its running time in terms of d and n.
e. Give an efficient implementation of INCREASE-KEY(A, i, k), which first sets A[i] $\leftarrow$ max(A[i], k) and then updates the d-ary max-heap structure appropriately. Analyze its running time in terms of d and n.

Solution:
a. Given an index i, we want to find its kth-child ($1 \leq k \leq d$). We can view $i = 1 + d + d^2 + \cdots + d^n + p = \frac{d^{n+1} - 1}{d - 1} + p$, where $1 \leq p \leq d^{n+1}$. The index of k-th child of A[i] is:
$i + (d^{n+1} - p) + (p-1)d + k = \frac{d^{n+1} - 1}{d - 1} + p + d^{n+1} - p + (i - \frac{d^{n+1} - 1}{d - 1} - 1)d + k$
$= \frac{d^{n+1} - 1}{d - 1} + d^{n+1} + id - \frac{d^{n + 2} - d}{d - 1} - d + k = id -d + 1 + k$
Therefore, we show how to get the index of k-th child of A[i]. Next we show how to get the index of parent of A[i]. We know nodes A[j] where $id - d + 1 + 1 \leq j \leq id - d + 1 + d$ have the same parent $i$. Trivially we know that $\lfloor \frac{j + (d - 2)}{d}\rfloor$ is the index of their parent.

@{
\proc{Child}(i, k)
\li \Return i \times d - d + 1 + k
}@


@{
\proc{Parent}(i)
\li \Return \lfloor \frac{i + (d - 2)}{d}\rfloor
}@

b. Let h be the height of a d-ary heap of n elements. Then we can obtain:
$1 + d + d^2 + \cdots + d^{h-1} +1 \leq n \leq 1 + d + d^2 + \cdots + d^h$
$\Rightarrow \frac{d^h - 1}{d - 1} < n \leq \frac{d^{h+1} - 1}{d - 1}$
$\Rightarrow d^h - 1 < (d - 1)n \leq d^{h + 1} - 1$
$\Rightarrow d^h \leq (d-1)n < d^{h+1}$
$\Rightarrow h \leq \log_d ((d-1)n) < h + 1$
$\Rightarrow h = \lfloor \log_d (d-1)n \rfloor$


c. We can develop a generalized version of EXTRACT-MAX in a manner as binary version. However, it should compare all its d children instead of 2 children.

@{
\proc{D-Ary-Max-Heapify}(A, i)
\li largest = i
\li \For j = 1 \;\textbf{to}\;k
\li \;\;\;\;p = i \times d - d + 1 + j
\li \;\;\;\;\If A[p] > A[largest]
\li \;\;\;\;\;\;\;\;largest = p
\li \If largest \not= i
\li \;\;\;\;\textup{exchange}\;A[i]\;\textup{and}\;A[largest]
\li \proc{D-Ary-Max-Heapify}(A, largest)
}@

@{
\proc{D-Ary-Extract-Max}(A)
\li \If \;\textit{heap-size}[A] < 1
\li \;\;\;\;\textbf{error}\;\textup{"heap underflow"}
\li max = A[1]
\li A[1] = A[\textit{heap-size}[A]]
\li \textit{heap-size}[A] = \textit{heap-size}[A] - 1
\li \proc{D-Ary-Max-Heapify}(A, 1)
\li \Return max
}@

The procedure D-ARY-EXTRACT-MAX implements the EXTRACT-MAX operation. The running time of D-ARY-EXTRACT-MAX is $O(d \log_d (d-1)n)$. Since each time we call D-ARY-MAX-HEAPIFY, it would check all its d children ($O(d)$). In the worst-case, the item will go down to a leaf, so takes $O( \log_d (d-1)n) * O(d) = O(d \log_d (d-1)n)$ time.


d. We can implement a generalized version of INSERT by updating operation PARENT with the operation which we derived in problem a. The running time is $O(\log_d (d-1)n)$


e. D-ARY-HEAP-INCREASE-KEY can be implemented as a slight modification of HEAP-INCREASE-KEY. The running time is $O(\log_d (d-1)n)$.

@{
\proc{D-Ary-Heap-Increase-Key}(A, i, k)
\li A[i] = \textup{max}(A[i], k)
\li \While i > 1 \;\textup{and}\; A[\proc{Parent}(i)] < A[i]
\li \;\;\;\;\textup{exchange}\;A[i]\;\textup{and}\;A[\proc{Parent}
(i)]
\li i = \proc{Parent}(i)
}@

Problem 6-3 Young tableaus
An $m \times n$ Young tableau is an $m \times n$ matrix such that the entries of each row are in sorted order from left to right and the entries of each column are in sorted order from top to bottom. Some of the entries of a Young tableau may be $\infty$, which we treat as nonexistent element. Thus, a Young tableau can be used to hold $r \leq mn$ finite numbers.
a. Draw a $4 \times 4$ Young tableau containing the elements {9, 16, 3, 2, 4, 8, 5, 14, 12}.
b. Argue that an $m \times n$ Young tableau Y is empty if $Y[1, 1] = \infty$. Argue that Y is full (contains mn elements) if $Y[m, n] < \infty$.
c. Give an algorithm to implement EXTRACT-MIN on a nonempty $m \times n$ Young tableau that runs in $O(m + n)$ time. Your algorithm should use a recursive subroutine that solves an $m \times n$ problem by recursively solving either an $(m-1) \times n$ or an $m \times (n-1)$ subproblem. (Hint: Think about MAX-HEAPIFY.) Define $T(p)$, where $p = m + n$, to be the maximum running time of EXTRACT-MIN on any $m \times n$ Young tableau. Give and solve a recurrence for $T(p)$ that yields the $O(m + n)$ time bound.
d. Show how to insert a new element into a nonfull $m \times n$ Young tableau in $O(m + n)$ time.
e. Using no other sorting method as a subroutine, show how to use an $n \times n$ Young tableau to sort $n^2$ numbers in $O(n^3)$ time.
f. Give an $O(m+n)$-time algorithm to determine whether a given number is stored in a given $m \times n$ Young tableau.

Solution:
a.   
 
There are other answers.


b. 
$Y[1, 1] = \infty$
If there are some element in $Y$, it should be larger than $\infty$. That's a contradiction.
$Y[m, n] < \infty$
If $Y$ is not full, then there should be some elements which is $\infty$. But $Y[m, n] < \infty$, it is a contradiction.


c.

@{
\proc{Young-Tableau-Min-Heapify}(Y, i, j, m, n)
\li \If i + 1 \leq m\;\textup{and}\;Y[i + 1, j] < Y[i, j]
\li \;\;\;\;largest = [i + 1, j]
\li \Else
\li \;\;\;\;largest = [i, j]
\li \If j + 1 \leq n \;\textup{and}\;Y[i, j+ 1] < Y[largest]
\li \;\;\;\;largest = [i, j + 1]
\li \If largest \not= [i, j]
\li \;\;\;\;\textup{exchange}\;Y[i, j] \;\textup{and}\;Y[largest]
\li \;\;\;\;\proc{Young-Tableau-Min-Heapify}(Y, largest, m, n)
}@

@{
\proc{Young-Tableau-Extract-Min}(Y, m, n)
\li min = Y[1, 1]
\li Y[1, 1] = \infty
\li \proc{Young-Tableau-Min-Heapify}(Y, 1, 1, m, n)
\li \Return min
}@

We can see that in the worst-case, the item in $Y[1, 1]$ has to be moved to $Y[m, n]$. There are m movements in vertical direction and n movements in horizontal direction. Each time we call YOUNG-TABLEAU-MIN-HEAPIFY, it will decrease one movement, therefore, its running time is $O(m + n)$. We can express the equation in such form:
$T(p) \leq T(p - 1) + \Theta(1) \Rightarrow T(p) = O(p)$


d.
@{
\proc{Young-Tableau-Insert-Bottom-Up}(Y, i, j, m, n)
\li \If i - 1 \geq 1\;\textup{and}\;Y[i -1 , j] > Y[i, j]
\li \;\;\;\;largest = [i - 1, j]
\li \Else
\li \;\;\;\;largest = [i , j]
\li \If j - 1 \geq 1 \;\textup{and}\;Y[i, j - 1] < Y[largest]
\li \;\;\;\;largest = [i, j - 1]
\li \If largest \not= [i, j]
\li \;\;\;\;\textup{exchange}\;Y[i, j]\;\textup{and}\;Y[largest]
\li \;\;\;\;\proc{Young-Tableau-Insert-Bottom-Up}(Y, largest, m , n)
}@


@{
\proc{Young-Tableau-Insert}(Y, m, n, key)
\li Y[m, n] = key
\li \proc{Young-Tableau-Insert-Bottom-Up}(Y, m, n, m, n)
}@


We insert an item into Young tableau in a bottom-up manner, and the running time is still $O(m + n)$.


e. Just run YOUNG-TABLEAU-EXTRACT-MIN iteratively for $n^2$ times, we can get the sequence in increasing sorted order. The running time is $n^2O(n + n) = O(n^3)$.


f. Consider the diagonal elements $Y[i, i]$, where $ 1 \leq i \leq min\{m, n\}$. We find the given number in these diagonal elements. If we can find it, it's done, otherwise we get two elemets $Y[j, j]$ and $Y[j+1, j+1]$ such that $Y[j, j] < x < Y[j+1, j+1]$, where x is the given number. Note that every $Y[p, q]$ where $j+1 \leq p$ and $j+1 \leq q$ are greater than $Y[j+1, j+1]$ and every $Y[r, s]$ where $r \leq j$ and $s \leq j$ are less than $Y[j, j]$. So we just try to search the other two blocks recursively. The running time can be written as:
$T(p) = 2T(p/2) + O(\log p)$
Using master theorem, we can derive that $T(p) = O(m + n)$