PPT Slide

• Prove that bubbledown(A,1) takes O(log n) time on a heap of length n.

public static void bubbledown(int A[], int i) { int child = 2 * i;

if (child<A.length && A[child + 1]>A[child]) {

++child;

if (child <= n && A[i] < A[child]){

swap(A,i,child);

bubbledown(A,child);

}

}

Previous slide

Next slide

Back to first slide

View graphic version