K largest(or smallest) elements in an array | added Min Heap method

Software Development
1

Hello Everyone,

Question: Write an efficient program for printing k largest elements in an array. Elements in array can be in any order.
For example, if given array is [1, 23, 12, 9, 30, 2, 50] and you are asked for the largest 3 elements i.e., k = 3 then your program should print 50, 30, and 23.

Method 1 (Use Bubble k times)

  1. Modify Bubble Sort to run the outer loop at most k times.
  2. Print the last k elements of the array obtained in step 1.
    Time Complexity: O(nk)

Method 2 (Use temporary array)
K largest elements from arr[0…n-1]

  1. Store the first k elements in a temporary array temp[0…k-1].
  2. Find the smallest element in temp[], let the smallest element be min .
    3-a) For each element x in arr[k] to arr[n-1]. O(n-k)
    If x is greater than the min then remove min from temp[] and insert x .
    3-b)Then, determine the new min from temp[]. O(k)
  3. Print final k elements of temp[]

Time Complexity: O((n-k)*k). If we want the output sorted then O((n-k)*k + klogk)
Thanks to nesamani1822 for suggesting this method.

Method 3(Use Sorting)

  1. Sort the elements in descending order in O(nLogn)
  2. Print the first k numbers of the sorted array O(k).

Following is the implementation of the above.

// C++ code for k largest elements in an array

#include <bits/stdc++.h>

using namespace std;

void kLargest( int arr[], int n, int k)

{

// Sort the given array arr in reverse

// order.

sort(arr, arr + n, greater< int >());

// Print the first kth largest elements

for ( int i = 0; i < k; i++)

cout << arr[i] << " " ;

}

// driver program

int main()

{

int arr[] = { 1, 23, 12, 9, 30, 2, 50 };

int n = sizeof (arr) / sizeof (arr[0]);

int k = 3;

kLargest(arr, n, k);

}

Output

50 30 23

Time complexity: O(nlogn)

Method 4 (Use Max Heap)

  1. Build a Max Heap tree in O(n)
  2. Use Extract Max k times to get k maximum elements from the Max Heap O(klogn)

Time complexity: O(n + klogn)

Method 5(Use Order Statistics)

  1. Use order statistic algorithm to find the kth largest element.
  2. Use QuickSort Partition algorithm to partition around the kth largest number O(n).
  3. Sort the k-1 elements (elements greater than the kth largest element) O(kLogk). This step is needed only if sorted output is required.

Time complexity: O(n) if we don’t need the sorted output, otherwise O(n+kLogk)