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