How to find the kth largest element in an array in C++

There are several methods to find the k^th largest element in a given array with N elements. The use of a sorting mechanism is at the heart of nearly all of them. However, one might naively implement an inefficient algorithm that takes O(N²) time in the worst case (and it is very easy and intuitive to do so using common techniques such as Bubble Sort or Selection Sort).

In this Answer, we will discuss two possible methods to efficiently find the kth largest element in an array.

1. Using a min-heap (heap sort)

Note that the k^th largest element in an array will obviously be the (N-k)^th smallest too. Hence, if we translate the problem as such, we can use min-heaps, which provide a useful method for extracting the smallest element in constant time.

Note: To learn more about min-heaps, refer to this link.

To implement our min-heap, we will choose the much simpler array implementation over a tree structure with left/right pointers. To track the parent and child element indices in such an implementation, we will use the following formula:

#include <iostream>
#include <climits>
#include <cstdlib>
#include <memory>
#include <vector>
using namespace std;
class MinHeap
{
    int* harr; // pointer to array of elements in heap
    int capacity; // maximum possible size of min heap
    int heap_size; // Current number of elements in min heap
public:
    // Constructor
    MinHeap(int cap);
    // return index of the parent of a node at index i
    int parent(int i);
    // get index of left child of node at index i
    int left(int i);
    // get index of right child of node at index i
    int right(int i);
    // remove minimum element (or root) from min heap
    int extractMin();
	int extractMinN_k(int k);
    // Returns the minimum key (key at root) from min heap
    int getMin();
    // Inserts a new key 'k'
    void insertKey(int k);
    // Helper function to percolateDown after editing the heap
    void percolateDown(int curr_index);
    // Helper function to percolateDown after editing the heap
    void percolateUp(int curr_index);
    int* getHeap();
};
MinHeap::MinHeap(int cap)
{
	capacity = cap;
	heap_size = 0;
	harr = new int[capacity];
}
int MinHeap::parent(int i)
{
	// formula for parent_index = floor[(i-1) / 2]
	int parent_index = (i-1) / 2;
	return parent_index;
}
 
int MinHeap::left(int i)
{
	// formula for left_child_index = 2i + 1
	int left_index = (2*i) + 1;
	return left_index;
}
 
int MinHeap::right(int i)
{
	// formula for right_child_index = 2i + 2
	int right_index = (2*i) + 2;
	return right_index;
}
void MinHeap::percolateUp(int curr_index)
{
	int child = curr_index;
	int parent = (child - 1) / 2;
	while(child > 0)
	{
		if(harr[child] < harr[parent])
		{
			int temp = harr[child];
			harr[child] = harr[parent];
			harr[parent] = temp;
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
 
void MinHeap::insertKey(int k)
{
	if(heap_size == capacity)
	{
		return;
	}
	harr[heap_size] = k;
	heap_size++;
	int child = heap_size - 1;
	int parent = (child - 1) / 2;
	percolateUp(child);
}
int MinHeap::extractMin()
{
	if(heap_size == 0)
	{
		return -1;
	}
	int min = getMin();
	if(heap_size == 1)
	{
		heap_size--;
	}
	if(heap_size > 1)
	{
		harr[0] = harr[heap_size-1];
		heap_size--;
		percolateDown(0);
	}
	return min;
}
 
void MinHeap::percolateDown(int curr_index)
{
	// percolate down
	int minimum_index = curr_index;
	if((left(curr_index) < heap_size) && (harr[left(curr_index)] < harr[minimum_index]))
	{
		minimum_index = left(curr_index);
	}
	if((right(curr_index) < heap_size) && (harr[right(curr_index)] < harr[minimum_index]))
	{
		minimum_index = right(curr_index);
	}
	if(minimum_index != curr_index)
	{
		int temp = harr[curr_index];
		harr[curr_index] = harr[minimum_index];
		harr[minimum_index] = temp;
		percolateDown(minimum_index);
	}
}
int MinHeap::extractMinN_k(int k) // calls extractMin a total of N-k times
{
	for(int i=0 ; i < heap_size ; i++)
	{
		extractMin();
	}
	return getMin();
}
int MinHeap::getMin()
{
	return harr[0];
}
int* MinHeap::getHeap()
{
	return harr;
}
int main()
{
	MinHeap* heap = new MinHeap(7);
	// MinHeap is a class that has the following members:
	// int* harr; // pointer to array of elements in heap
    // int capacity; // maximum possible size of min heap
    // int heap_size; // Current number of elements in min heap
	
	int num_of_elements = 7 ; // number of elements in this example
	int heap_values[7] = {3, 6, 23, 1, 4, 0, 14};
	
	// printing the array:
	cout << "Array: " ;
	for(int i=0 ; i<num_of_elements ; i++)
	{
		cout << heap_values[i] << " " ;
	}
	cout << endl ;
	for(int i = 0; i < num_of_elements; i++)
	{
		heap->insertKey(heap_values[i]); // the implementation of insertKey is hidden, but it just adds a new element to the heap
	}
	int k=3 ;
	heap->extractMinN_k(k);
	
	cout << endl ;
	cout << "\nkth largest element (where k = " << k << ") is: " << heap->getMin() ;
}

Explanation

Lines 116–170: percolateDown implements the following steps to maintain the heap-order property A parent’s key is always ≤ both its children’s keys. once the minimum (element at index 0) is removed by extractMin:
- We move the element at the last index into the hole left at index 0 by removing the minimum, and decreasing the total count of elements stored in the heap.
- Starting from index 0, we compare the parent element with its children and replace the parent with its smallest child.
Time complexity: This is O(NlogN), since removing each element from the heap takes O(logN) time, and a total of n elements need to be removed in the worst case (k=size of the given array).
Space complexity: This is O(N), since a new array is made to store the heap.

Note: Heap sort can be implemented in O(1) space complexity as well. This can be done by converting the given array into a heap, in-place (Floyd's method). The steps involved in this method are as follows:
Put all the elements anywhere in the array (instead of inserting elements one-by-one and maintaining the heap-order property).
Treat the array as a heap and fix the heap-order property.
Refer to this link to see the implementation of Floyd's method to heapify an array.

2. Using a Quicksort variation

Similar to the first method, if we translate the problem such that instead of searching for the k^th largest element, we search for the (N-k)^th smallest element, we can use a variation of the quick sort algorithm and find an efficient solution. The steps are depicted in the figure below, along with an example.

#include <iostream>
using namespace std;
void swapElements(int* arr, int i, int j) 
{
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
int findKthLargest(int* arr, int k, int arr_size) 
{
  if (arr_size == 1) 
  {
    return arr[0];
  }
 
  int low = 0;
  int high = arr_size- 1;
  int target_index = arr_size - k;
 
  while (1) 
  {
    if(low <= high)
    {
        int ind = low;
        for (int i = ind; i < high; i++) 
        {
            if (arr[i] < arr[high]) 
            {
                swapElements(arr, ind, i);
                ind++;
            }
        }
        swapElements(arr, ind, high);
        if (ind > target_index) 
        {
            high = ind - 1;
            continue;
        } 
        else if (ind < target_index) 
        {
            low = ind + 1;
            continue;
        } 
        return arr[ind];
    }
    else
    {
        break;
    }
  } 
}
int main()
{
    int size_of_array = 6; // size of array in thighs example
    int arr[6] = {3,2,1,5,6,4};
    int k = 4;
    cout << "kth largest (where k=" << k << ") is: " << findKthLargest(arr , k, size_of_array);
}

Free Resources