`Bubble-Down`(A,i,n) is specified as follows on a 1-based array that is a complete…

`Bubble-Down`(\(A,i,n\)) is specified as follows on a 1-based array that is a complete binary tree. Let \(L\) and \(R\) be the left and right children of \(i\) (if they exist). If \(i\) has no child with a strictly smaller key than \(A[i]\), return. Otherwise let \(j\) be a child of \(i\) of minimum key (break ties toward the left child) and swap \(A[i]\) with \(A[j]\); then recurse (or iterate) at \(j\). Prove the following invariant: if every subtree rooted at a proper descendant of \(i\) is a min-heap, then after `Bubble-Down`(\(A,i,n\)) returns, the subtree rooted at \(i\) is a min-heap. Your proof must handle the cases of zero, one, and two children, and must argue that a swap cannot violate heap order at the parent of the original \(i\) (the parent is outside the subtree under consideration). Conclude that Floyd's `Build-Heap`, which calls `Bubble-Down` on nodes in decreasing index order, produces a min-heap.

The recursive step only fires when \(i\) is larger than a child; after the swap, \(i\) holds that smaller child and the hole has moved down.