Problems
6-1
a
Let A = [1, 2, 3, 4]
, if we use BUILD-MAX-HEAP
, we have A = [4, 2, 3, 1]
. If we use BUILD-MAX-HEAP'
, we have A = [4, 3, 2, 1]
. That's a counterexample.
b
The worst-case happens when A is in increasing order, in each iteration, MAX-HEAP-INSERT(A, A[i])
requires $O(\lg{k})$ to heapify the heap (move A[i]
from bottom to top), where k is the number of elements in heap. Thus the running time is $\sum_{i = 2}^{n}\lg{i} = \lg{(n!)} = \Theta(n\lg{n})$.
6-2
a
For a node with index i (i = 1, 2, ..., n), its kth child index is d(i - 1) + k + 1
in array, and its parent's index is $\lceil \frac{i - 1}{d} \rceil$.
b
The max number of elements in d-ary heap is $d^0 + d^1 + \ldots + d^h = \sum_{i = 0}^{h}d^h = \frac{d^{h + 1} - 1}{d - 1}$, the min number of elements in d-ary heap is $d^0 + d^1 + \ldots + d^{h - 1} + 1 = \sum_{i = 0}^{h}d^{h - 1} + 1 = \frac{d^h - 1}{d - 1} + 1$. Thus, $\frac{d^h - 1}{d - 1} + 1 \leq n \leq \frac{d^{h + 1} - 1}{d - 1}$.
For a d-ary heap, we have $d \geq 2$. Let's check the left part first. $\frac{d^h - 1}{d - 1} + 1 = \frac{d^h - 1 + (d - 2)}{d - 1} \geq \frac{d^h - 1}{d - 1}$, so $h \leq \log_d{(n(d - 1) + 1)}$. And:
$$ \begin{eqnarray} \log_d{(n(d - 1) + 1)} - (\log_d{(n(d - 1))} + 1) &=& \log_d{(\frac{1}{d}(1 + \frac{1}{n(d - 1)}))} \\ &\leq& \log_d{(\frac{1}{d}(1 + \frac{1}{d - 1}))} \\ &=& \log_d{\frac{1}{d - 1}} \\ &\leq& \log_d{\frac{1}{\frac{d}{2}}} \\ &=& \log_d{\frac{2}{d}} \\ &=& \log_d2 - 1 \\ &\leq& \log_2{2} - 1 \\ &=& 0 \end{eqnarray} $$
So $\log_d{(n(d - 1) + 1)} \leq \log_d{(n(d - 1))} + 1$, if n = 1 and d = 2, we have $\log_d{(n(d - 1) + 1)} = \log_d{(n(d - 1))} + 1$, for a d-ary heap, n is usually not 1, so we can say $\log_d{(n(d - 1) + 1)} < \log_d{(n(d - 1))} + 1$. Thus we have $h < \log_d{(n(d - 1))} + 1$.
Then let's check the right part. $\frac{d^{h + 1} - 1}{d - 1} < \frac{d^{h + 1}}{d - 1}$, so $h > \log_d{(n(d - 1))} - 1$.
So $h = \lfloor \log_d{(n(d - 1))} \rfloor$.
c
It's similar like EXTRACT-MAX
2-ary heap. The running time of EXTRACT-MAX
for d-ary heap is mainly the running time of MAX-HEAPIFY
. We need to change MAX-HEAPIFY
a little bit.
MAX-HEAPIFY(A, i)
largest = i
for i = 1 to d
child = CHILD(i)
if child <= A.heap-size and A[child] > A[largest]
largest = child
if largest != i
exchange A[i] with A[largest]
MAX-HEAPIFY(A, largest)
So the running time of MAX-HEAPIFY
for d-ary heap is $O(dh) = O(d\log_d{(n(d - 1))})$.
d
The INSERT
method only compares node i with its parent, so the running time is $O(h) = O(\log_d{(n(d - 1))})$.
e
Since the INSERT
method calls INCREASE-KEY
method, the running time of INCREASE-KEY
is also $O(h) = O(\log_d{(n(d - 1))})$.
6-3
a
$$ \begin{matrix} 2 & 3 & 4 & 5 \\ 8 & 9 & 12 & 14 \\ 16 & \infty & \infty & \infty \\ \infty & \infty & \infty & \infty \end{matrix} $$
b
If $Y[1, 1] = \infty$, then no cell can has a value greater than Y[1, 1]
, other cells are all $\infty$, so Y is empty.
Y[m, n]
is the largest in Y, if it's not $\infty$, then others are also not $\infty$, so Y is full.
c
Y[1, 1]
is the smallest, after we extract it, we need to make Y to a Young tableau again.
First we start at Y[1, 1]
, then we compare its right element and below element, if right element is smaller than below element, we put right element to Y[1, 1]
, which makes Y[1, 1]
to Y[1, m]
sorted, but Y[1, 2]
to Y[m, n]
might be not a Young tableau.
if right element is greater than below element, we put below element to Y[1, 1]
, which makes Y[1, 1]
to Y[1, n]
sorted, but Y[2, 1]
to Y[m, n]
might be not a Young tableau.
EXTRACT-MIN(Y)
smallest = Y[1, 1]
Y[1, 1] = ∞
YOUNGIFY(Y, 1, 1)
return smallest
YOUNGIFY(Y, row, column)
smallest_row = row
smallest_column = column
if row + 1 <= m and Y[row + 1, column] < Y[row, column]
smallest_row = row + 1
if column + 1 <= n and Y[row, column + 1] < Y[smallest_row, smallest_column]
smallest_row = row
smallest_column = column + 1
if smallest_row != row or smallest_column != column
exchange Y[row, column] with Y[smallest_row, smallest_column]
YOUNGIFY(Y, smallest_row, smallest_column)
After each recursive procedure, the YOUNGIFY
method cuts a row or a column, which reduces the problem size to (m - 1) x n or m x (n - 1). Notice that both (m - 1) + n = m + n - 1 and m + (n - 1) = m + n - 1, so m + n is decreased by 1 in each recursive procedure. so T(p) = T(p - 1) + O(1), it's obvious to know that T(p) = O(p) = O(m + n).
d
Similar like EXTRACT-MIN
, we first put the new element to Y[m, n]
, then youngify the tableau from Y[m, n]
. The running time is O(m + n).
INSERT(Y, key)
Y[m][n] = key
YOUNGIFY-INSERT(Y, m, n)
YOUNGIFY-INSERT(Y, row, column)
largest_row = row
largest_column = column
if row - 1 >= 1 and Y[row - 1][column] > Y[row][column]
largest_row = row - 1
if column - 1 >= 1 and Y[row][column - 1] > Y[largest_row][largest_column]
largest_row = row
largest_column = column - 1
if largest_row != row or largest_column != column
exchange Y[row, column] with Y[largest_row, largest_column]
YOUNGIFY-INSERT(Y, largest_row, largest_column)
e
The INSERT
operation takes O(n + n) = O(n) time, and there are $n^2$ elements, so we can insert each element into the n x n Young tableau, thus the running time is $n^2O(n) = O(n^3)$.
f
We start from Y[m, 1]
, and compare Y[m, 1]
with target value, if Y[m, 1]
is greater than target value, we move to Y[m - 1, 1]
, if it's smaller than target value, we move to Y[m, 2]
, otherwise, we find the target value.
FIND(Y, key)
row = m
column = 1
while row >= 1 and column <= n
if Y[row][column] == key
return True
else if Y[row][column] < key
column += 1
else if Y[row][column] > key
row -= 1
return False
Similar like YOUNGIFY
, it reduces the problem size to (m - 1) * n or m * (n - 1), so the running time is O(m + n).