Question

Give pseudocode for a Theta(n)-time algorithm that returns the 50 largest values in an array. You may assume the array has at least 50 values.

Answer 1

/*If you have any query do comment in the comment section else like the solution*/

Pseudo Code:

function FiftyLargest(arr, size) {
   PriorityQueue pq = createMaxHeap(arr, size);
   for i = 0 to 49
       print(pq.top())
       pq.pop()
}

function createMaxHeap(arr, n) {
   PriorityQueue pq
   for i = 0 to n
       pq.add(arr[i])
   return pq;
}

Time taken to create maxHeap = O(n) //where n is size of array

Time taken to pick 50 largest element = O(k log n) // where is k is 50

Overall time complexity = O(n + klogn)