Procedure Heapify
Book algorithm:
- Heapify(A,i)
- L = left(i);
- R= right(i);
- if ( L <= heapsize[A] and A[R]> A[i]
- largest=L;
- else
- largest=i;
- if (R <= heapsize[A] and A[R] > A[largest]
- largest=R
- if largest != i
- exchange A[i] with A[largest]
- Heapify(A,largest);
Explanation:
Consider element i and its left and right children.
select the largest element of those.
if element i is the largest, then this subtree is a heap. end of procedure
if not, swap element i with the largest element. Element i and its children are now a
heap, but since the tree has changed, further recursive calls to hepify are needed to
restore the heap.
Notes for a C implementation:
Notice that the parameters will be:
void heapify(aheap *A, int i)
therefore the size of A is: A->heapsize
elements are still A[i], A[R], etc.
What is the running time of this procedure?
Running time is proportional to the height of the node. O(h). If tree has n nodes,
running time is O(lg n)