Heap: Kth smallest element.

Problem Statement:

You are given an unsorted array of integer elements and “k”. You need to get the “k”th smallest element.

Example

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

Output: 7.

Solution

Before we start the solution, let us understand few points related to heap and identification of heap related questions.

1. identification of heap related questions:

a. If in a question, there is a “K” and it has something related to “smaller” “larger” keyword then the question is of heap.

In heap there are 2 types of heap.

For a binary heap:
arr[(i-1)/2]	Returns the parent node
arr[(2*i)+1]	Returns the left child node
arr[(2*i)+2]	Returns the right child node

If k + smallest, then take max heap in the solution
If k + largest, then take min heap in the solution

Why?

When you create a min heap to get the kth largest element, all the elements on top of k will be smaller. we can remove all the minimum elements till “k”. Hence we will get the solution easily.

Most of the heap related questions can be solved by sorting. The best complexity can be got by sorting is “nlogn” if you use merge sort.
Then if you use heap with “k”, then the complexity will be reduced to “nlogk”.

In max heap, the max element will be on top
In min heap, the min element will be on top

In C++, heaps are represented by priority_queue:

1. For Max Heap: priority_queue<int> max_heap;

2. For Min Heap: priority_queue<int, vector<int>, greater<int>> min_heap;

In any question, if we need a pair, then replace “int” with “pair”.

Coming to the question, we need to find the kth smallest element. So we need to use Max Heap.

So if you use sorting the time complexity will be nlogn.
If we use heap, it can be reduced to nlogk.

Input:

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

Now we will represent Maxheap as stack:

Pass 1:

Element = 7
Stack = 7

Pass 2:

Element = 10
Stack = 7 10

Pass 2:

Element = 4
Stack = 4 7 10

Pass 3:

Element = 3
Stack = 3 4 7 10

Now the size is greater than 3, then we pop 10. Because we know that 10 will not be in the kth smallest element.

Pass 4:

Element = 20
Stack = 3 4 7

We will not add 20 also, because its grater and the heap size is already equal to k.

Pass 5:

Element = 15
Stack = 3 4 7

We will not add 15 also, because its grater and the heap size is already equal to k.

Now top of the stack will have the result i.e “7”.

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <queue> 
#include <list> 

using namespace std;

void kth_smallest_element(vector<int>& v,int k)
{
    //max_heap
    priority_queue<int> max_heap;

    int n = v.size();
 
    for (int i = 0; i < n; ++i) 
    {
        //keep inserting elements into the heap
        max_heap.push(v[i]);
 
        // if the size exceeds K,
        // then start popping the elements
        if (max_heap.size() > k) 
        {
            max_heap.pop();
        }
    }
    
    //print the top of the heap to get the result. 
    cout << "The result is "<< max_heap.top() << endl;
}
 
int main()
{
    vector<int> vec = { 7, 10, 4, 3, 20, 15};
 
    int k = 3;
 
    kth_smallest_element(vec, k);
 
    return 0;
}

Output:

The result is 7