# Cormen Edition 3 Exercise 6.2 Question 5 (Page No. 156)

27 views

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.

## Related questions

1
20 views
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 MAXHEAPIFY to be called recursively at every node on a simple path from the root down to a leaf).
What is the effect of calling MAX-HEAPIFY$(A,i)$ for $i > A.heapsize/2$.
What is the effect of calling MAX-HEAPIFY$(A, i)$ when the element $A[i]$ is larger than its children?
Starting with the procedure MAX-HEAPIFY, write pseudocode for the procedure MIN-HEAPIFY$(A, i )$, which performs the corresponding manipulation on a minheap. How does the running time of MIN-HEAPIFY compare to that of MAXHEAPIFY?