[Algo] Exercise 6.2

Exercise 6.2-2
Starting with the procedure MAX-HEAPIFY, write pseudocode for the procedure MIN-HEAPIFY(A, i), which performs the corresponding manipulation on a min-heap. How does the running time of MIN-HEAPIFY compare to that of MAX-HEAPIFY?

@{
\proc{Min-Heapify}(A, i)
\li l = \proc{Left}(i)
\li r = \proc{Right}(i)
\li \If l \leq \;\textit{heap-size}[A]\;\textup{and}\;A[l] < A[i]
\li \;\;\;\;smallest = l
\li \Else
\li \;\;\;\;smallest = i
\li \If r \leq \;\textit{heap-size}[A]\;\textup{and}\;A[r] < A[smallest]
\li \;\;\;\;smallest = r
\li \If smallest \not= i
\li \;\;\;\;\textup{exchange}\;A[i]\;\textup{and}\;A[smallest]
\li \;\;\;\;\proc{Min-Heapify}(A, smallest)
}@

Its running time is the same as subroutine MAX-HEAPIFY, $O(\lg n)$


Exercise 6.2-3
What is the effect of calling MAX-HEAPIFY(A, i) when the element A[i] is larger than its children?
It will do nothing, because it satisfies the max-heap property.


Exercise 6.2-4
What is the effect of calling MAX-HEAPIFY(A, i) for i > heap-size[A]/2?
From exercise 6.1-7, we know they are leaves of the heap, and for a leaf, there is no child. MAX-HEAPIFY will do nothing and just return.


Exercise 6.2-5
The code for MAX-HEAPIFY is quite efficient in terms of constant factors, except possibly for the recursive call in line 10, which might cause some compilers to produce inefficient code. Write an efficient MAX-HEAPIFY that uses an iterative control construct (a loop) instead of recursion.
@{
\proc{Iterative-Max-Heapify}(A, i)
\li \While i \leq \;\textit{heap-size}[A]
\li \;\;\;\;l = \proc{Left}(i)
\li \;\;\;\;r = \proc{Right}(i)
\li \;\;\;\;\If l \leq \;\textit{heap-size}[A] \;\textup{and}\; A[l] > A[i]
\li \;\;\;\;\;\;\;\;largest = l
\li \;\;\;\;\Else
\li \;\;\;\;\;\;\;\;largest = i
\li \;\;\;\;\If r \leq \;\textit{heap-size}[A] \;\textup{and}\; A[r] > A[largest]
\li \;\;\;\;\;\;\;\;largest = r
\li \;\;\;\;\If largest \not= i
\li \;\;\;\;\;\;\;\;\textup{exchange}\;A[i]\;\textup{and}\;A[largest]
\li \;\;\;\;\Else
\li \;\;\;\;\;\;\;\;\textup{break the loop}
}@

Exercise 6.2-6
Show that the worst-case running time of MAX-HEAPIFY on a heap of size n is $\Omega(\lg n)$. (Hint: For a heap with n nodes, give node values that cause MAX-HEAPIFY to be called recursively at every node on a path from the root down to a leaf.)
For a heap with n nodes, the worst-case is that a node value causing MAX-HEAPIFY to be called recursively at every node on a path from the root down to a leaf. The running time is $\Theta(1)$ for fixing up the relationships among the elements A[i], A[LEFT(i)] and A[RIGHT(i)]. If the height of a heap is h, the running time is $(h + 1)\cdot\Theta(1) = \Theta(h) = \Theta(\lg n)$. So we prove that it requires $\Omega(\lg n)$ time.