The procedure BUILD-MAX-HEAP in Section 6.3 can

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.

Members

  • Access to 2 Million+ Textbook solutions
  • Ask any question from 24/7 available
    Tutors
$9.99
VIEW SOLUTION

OR

Non-Members

Get help from Computer Sciences Tutors
Ask questions directly from Qualified Online Computer Sciences Tutors .
Best for online homework assistance.