Question

5. Answer the following.

(a) (5 points) Suppose you are given a maxheap of n unique numbers. Explain where will the smallest of these n numbers be located in the maxheap. Explain where will the second largest number be located on this maxheap. Please be specific.

(b) (5 points) Suppose you are given an array A of n numbers, where all the elements of the array are already sorted in decreasing order. Is this a max-heap? Explain.

(c) (5 points) Suppose you have a max-heap of n elements. Is the corresponding array sorted in decreasing order? Explain.

(d) (5 points) Suppose an array A contains n identical numbers. What is the running time of randomized quicksort on A?

5. Answer the following. (a) (5 points) Suppose you are given a maxheap of n unique numbers. Explain where will the smallest of these n numbers be located in the maxheap. Explain where will the second largest number be located on this maxhcap. Please be specific. (b) (5 points) Suppose you are given an array A of n numbers, where all the elements of the array are already sorted in decreasing order. Is this a max-heap? Explain. (c) (5 points) Suppose you have a max-heap of n elements. Is the corresponding array sorted in decreasing order? Explain. (d) (5 points) Suppose an array A contains n identical numbers. What is the running time of randomized quicksort on A?

Answer 1

a) The smallest node will be stored in leaf node of the max heap.

The second largest node will be either of the 2 children of root node (which is the largest node itself).

================

b) Yes it is max heap.

Let the array be A[n] with 0 based indexing.

Any node i, will have max 2 children with index i*2 + 1 and i*2 + 2.

Since both i*2 + 1 and i*2 + 2 are greater than i and array is sorted in descending order, we can say that for any node i, it's children are smaller than it. Hence max heap property is satisfied for every node.

========================

c) No. Not it is not a neccessary condition for array to sorted in descending order.But sorted array in descending order is always a max heap.

See the example of max heap : A = { 10 , 6, 8 , 1 ,2,3,4}

The above array is clearly a max heap.

10 has two childs 6,8 which are smaller than 10.

6 has two childs 1,2 which are smaller than 6

8 has two childs 3,4 which are smaller than 8.

So A is a max heap. But A is not sorted is descending order.

========================

d) O(n^2) same as worst case

Pivot divides array in two parts left and right. All elements are identical so choice of pivot doesn't effect distribution.

Further, Since all the elements are identical, one of the half will always be empty. Thus, leading to worst case performance of O(n^2).

==========================

Please upvote

for any query comment