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

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).