K’th Smallest/Largest Element in Unsorted Array (Using Min Heap - Heap Select)

Software Development
#1

Hello Everyone,

Given an array and a number k where k is smaller than the size of the array, we need to find the k’th smallest element in the given array. It is given that all array elements are distinct.

Examples:

Input : arr[] = {7, 10, 4, 3, 20, 15}
k = 3
Output : 7

Input : arr[] = {7, 10, 4, 3, 20, 15}
k = 4
Output : 10

Method Using Min Heap – HeapSelect)
We can find k’th smallest element in time complexity better than O(N Log N). A simple optimization is to create a Min Heap of the given n elements and call extractMin() k times.

The following is C++ implementation of above method.

// A C++ program to find k'th smallest element using min heap

#include <climits>

#include <iostream>

using namespace std;

// Prototype of a utility function to swap two integers

void swap( int * x, int * y);

// A class for Min Heap

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 :

MinHeap( int a[], int size); // Constructor

void MinHeapify( int i); // To minheapify subtree rooted with index i

int parent( int i) { return (i - 1) / 2; }

int left( int i) { return (2 * i + 1); }

int right( int i) { return (2 * i + 2); }

int extractMin(); // extracts root (minimum) element

int getMin() { return harr[0]; } // Returns minimum

};

MinHeap::MinHeap( int a[], int size)

{

heap_size = size;

harr = a; // store address of array

int i = (heap_size - 1) / 2;

while (i >= 0) {

MinHeapify(i);

i--;

}

}

// Method to remove minimum element (or root) from min heap

int MinHeap::extractMin()

{

if (heap_size == 0)

return INT_MAX;

// Store the minimum vakue.

int root = harr[0];

// If there are more than 1 items, move the last item to root

// and call heapify.

if (heap_size > 1) {

harr[0] = harr[heap_size - 1];

MinHeapify(0);

}

heap_size--;

return root;

}

// A recursive method to heapify a subtree with root at given index

// This method assumes that the subtrees are already heapified

void MinHeap::MinHeapify( int i)

{

int l = left(i);

int r = right(i);

int smallest = i;

if (l < heap_size && harr[l] < harr[i])

smallest = l;

if (r < heap_size && harr[r] < harr[smallest])

smallest = r;

if (smallest != i) {

swap(&harr[i], &harr[smallest]);

MinHeapify(smallest);

}

}

// A utility function to swap two elements

void swap( int * x, int * y)

{

int temp = *x;

*x = *y;

*y = temp;

}

// Function to return k'th smallest element in a given array

int kthSmallest( int arr[], int n, int k)

{

// Build a heap of n elements: O(n) time

MinHeap mh(arr, n);

// Do extract min (k-1) times

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

mh.extractMin();

// Return root

return mh.getMin();

}

// Driver program to test above methods

int main()

{

int arr[] = { 12, 3, 5, 7, 19 };

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

cout << "K'th smallest element is " << kthSmallest(arr, n, k);

return 0;

}

Output:

K’th smallest element is 5

Time complexity of this solution is O(n + kLogn).