Question

Heaps
Given a max heap write a separate procedure for each to find the
• max value
• second largest value
• third largest value
• min value
• Prove using a proof by contradiction that the min value is in a leaf
Quicksort
Professor Sample says that he thinks the average of three random values makes sense as a pivot value. Is he right? why is this not a bad choice or is bad.
What happens with the partition algorithm in the text if all the values in the array are equal.

Answer 1

For finding the max element in the max heap we just need to return the 0th index of the max heap array.

int maxvalue(int arr[],int n)

{

int maxelement=arr[0];

return maxelement;

}

For finding the second largest value we need to:-

1)extract max element from the maxheap

2)and then heapify and

3)extract max element from the heap

public int extractMax(int arr[],int n)

    {

        int popped = arr[1];

arr[1] = arr[n--];

        maxHeapify(1);

        return popped;

    }

int secondmaxvalue(int arr[],int n)

{

extractMax(arr,n);

int secondmaxelement=arr[0];

return secondmaxelement;

}

For finding the third largest value we need to:-

1)extract max element from the maxheap

2)and then heapify and

3)extract max element from the heap

4)heapify

5)extract max element

int thirdmaxvalue(int arr[],int n)

{

extractMax(arr,n);

extractMax(arr,n);

int thirdmaxelement=arr[0];

return thirdmaxelement;

}

For finding the minimum value of the max heap:-

int findMinimumElement(int arr[], int n)

{

    int minimumElement = arr[0];

    for (int i = 1; i < n; ++i)

        minimumElement = min(minimumElement, arr[i]);

    return minimumElement;

}

Prove using a proof by contradiction that the min value is in a leaf

Prove by contradiction. Assume that the minimum value is a node, which is not the leaf. Then, it has atleast one child, and that has a value smaller than the node. Contradiction.

Professor Sample says that he thinks the average of three random values makes sense as a pivot value. Is he right? why is this not a bad choice or is bad.

The constant for the usual randomized quicksort is easy to compute because the probability that two elements k locations apart are compared is exactly 2/(k+1): the probability that one of the those two elements is chosen as a pivot before any of the k-1 elements between them.

What happens with the partition algorithm in the text if all the values in the array are equal.

Total O(n*n) comparisons have to be made.