a) If a heap is used to represent a priority queue, and the first element is removed, the heap property is restored by moving the last element to the root of the tree, and then running MAX-HEAPIFY on the new root element. What is the worst-case complexity of restoring the heap property in this way?

b) The first step of the heapsort algorithm converts the input array into a max heap using a function called BUILD-MAX-HEAP. Surprisingly, the worst- case complexity of this function is linear in the size n of the input array.

c) Consider a large, unsorted file of records that contains many duplicates of the same records. (One record is a duplicate of another if it has the same record number.) Consider the problem of removing all of the duplicates, so that the file contains a unique copy of each record. Describe a simple algorithm that removes all duplicates and runs in O(n log n) time, where n is the number of records in the file.

d) Consider the following recurrence: T (n) = 3T(n/2) + n. Indicate which case b of the Master theorem applies (first, second, or third), and solve the recurrence.

 

The following recursive algorithm finds the sum of all elements in an array using a divide and conquer strategy. func sumArray(A, low, high) if low > high return 0 if low = high %3D return A[low] mid