Design and Analysis of Algorithms

A. Consider the array A = <18, 10, 14, 3, 5, 7, 15, 12, 25, 80>.

1) write A after calling the function BUILD-MAX-HEAP(A)

2) write A after calling the function HEAP-INCREASE-KEY(A,9,50).

3) write A after calling the function HEAP-EXTRACT-MAX(A)

Part 2) uses the array A resulted from part 1). Part 3) uses the array A resulted from part 2).

* Note that HEAP-INCREASE-KEY and HEAP-EXTRACT-MAX operationsare implemented in the Priority Queue .

B. Let A[1...n] be a max-heap, where n > 1 and n is even. Then A[n2+1...n] is a max-heap. (True or False)