The procedure BUILD-MAX-HEAP in Section 6.3 can be implemented by repeatedly using MAX-HEAP-INSERT to insert the elements into the heap. Consider the following implementation:
BUILD-MAX-HEAP'(A)
1 heap-size [A] ← 1
2 for i ← 2 to length [A]
3 do MAX-HEAP-INSERT (A, A[i])
a. Do the procedures BUILD-MAX-HEAP and BUILD-MAX-HEAP' always create the same heap when run on the same input array? Prove that they do, or provide a counterexample.
b. Show that in the worst case, BUILD-MAX-HEAP' requires Θ (n lg n) time to build an n-element heap.