kth_largest_element

Kth Largest Element in an Unsorted Array

Algorithm

int kth_largest_element(vector<int> arr, int k)
{
  priority_queue<int, vector<int>, greater<int>> minH;
  int n = arr.size();

  // if the input is invalid
  if (n < k || k < 1)
    return -1;

  // insert initial k elements into the heap
  for (int i = 0; i < k; i++)
    minH.push(arr[i]);

  // now remove the top element after inserting each element
  for (int i = k; i < n; i++)
  {
    minH.push(arr[i]);
    minH.pop();
  }

  // return the top element of the heap
  return minH.top();
}

Complexity

• Time:
  • Worst Case:
  • Average Case:
  • Best Case:
• Space:
  • Worst Case: