Given an array A of n numbers, consider the problem of returning the i largest e

Question

Given an array A of n numbers, consider the problem of returning the i largest elements of A in sorted order. For each of the following algorithms, give estimates for the worst-case running time in terms of n and i, justifying each answer. Sort A using Heap sort, and list the i largest. Build a max-priority queue from the numbers, and call Heap Extract Max i times. Use the order-statistic algorithm described on page 220 to find the i th order statistic, then partition around that element, and then sort the i largest numbers using Merge Sort.

Explanation / Answer

1. worst case complexity for heap sort

in this method we sort the ENTIRE array, and then use indexing to get the ith largest.

to find the complexity we must know the steps involved in this process.

step i - first we need to build a MAX heap with the given data input . this will take O(n)

step ii - the max value of the array is now at the root, then replacee it with heap's last item,then decreasee the sizze of the heap by 1 . then REHEAP with step 1. do this till size of the heap becomes 1.   

Now, we need to know the number of times step ii will be initiated. multiplying it with O(n) will give us the complexity overall!

let us look at the code for step ii,

void heapify(int arr[], int n, int i)

{

    int largest = i;

int l = 2*i + 1;

    int r = 2*i + 2;

if (l < n && arr[l] > arr[largest])

        largest = l;

if (r < n && arr[r] > arr[largest])

        largest = r;

if (largest != i)

    {

        swap(arr[i], arr[largest]);

heapify(arr, n, largest);

    }

}

this is similar to merge sort, and the recursion will be called log n times likewise! so, we will be reheaping log n times each with complexity O(n). so = O(nlogn) is overall complexity. then , the array will be sorted, and the ith largest will simply be arr[size - i - 1] with O(1)

so overall complexity O(nlogn)

--------------------------------------------------------

2.

here we will build a max heap like abovee with O(n)

then the extract max function will extract the max element from the heap and return the remaining heap for heapify! this will go for i iterations! as the ith largest number will be the root of the max heap in the ith iteration.

complexity of 1 extract max - O(logn) .

this will go for i iterations so O(ilogn)

overall ccomplexity - O(n + ilogn)

------------------------------------------------------

3.

the book has not been specified so the question is ambigious.

however the ith order statistic can be found out in O(n) time (using the quick parttion)

then to sort the remaining array as asked in the question with merge sort we will have O(nlong)

but the number of elements remain are i - so complexity is O(ilogi)

therefore , overall complexity is O(n + ilogi)

--------------------------------------------------------------------

thank you

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.