K-th Smallest Element in the Unsorted Array using a Priority Queue

Introduction

Priority Queue is a wonderful Data Structure having a wide range of applications and is implemented using Heap Data Structure. Numerous amounts of problems are based on the concepts of priority queues. It is an important Data Structure when it comes to technical interviews of top tech companies as well. In this article, we will cover one such problem. 

This blog discusses the to find the K-th smallest element in the unsorted array by using a Priority queue.

There could be many ways to find the K-th smallest element, but in this blog, we discussed the method, which is solved by using the data structure Priority queue.

Priority Queue: Priority Queue is basically an implementation of the heap. Let’s know more about the Priority queue.

The problem states that Given an array consisting of n unsorted integers and an integer K, the task is to find the K-th smallest element in the array using a data-structure  Priority queue.

Also see, Implementation of Heap

E.g:

Input: 

n  = 5, K= 3
array = [5, 3, 7, 8, 10] 

Output: 

7

Recommended: Try the Problem yourself before moving on to the solution.

Approach 

The approach to this problem is quite simple. We use a Max-heap to find the K-th smallest element in an unsorted array.

Algorithm

• Construct a max-heap.
• Insert the first K elements of array [0…K-1] into the max-heap.
• Then for the remaining elements of array[k…n-1],
  • Push the element one by one in a max heap and check if the size of the heap is greater than K, then pop the top element.
  • Repeat the above process till the array is exhausted.
• Return the top element of the max heap. This is K-th smallest element.

Implementation in C++

#include <bits/stdc++.h>

using namespace std;

// Fuction to find K-th smallest element
int Kth_smallest(int arr[], int n, int K) {
    // create a max heap
    priority_queue < int > pq;
    // insert first K element in queue
    for (int i = 0; i < K; i++) {
        pq.push(arr[i]);
    }
    // interest the remaining element
    for (int i = K; i < n; i++) {
        pq.push(arr[i]);
        if (pq.size() > K)
            pq.pop();
    }
    // return K-th smallest element
    return pq.top();
}
//Driver function.
int main() {
    int n;
    n = 5; // size of array
    int arr[] = { 5, 3, 9, 2, 7 };
    int K;
    K = 3;
    int ans = Kth_smallest(arr, n, K);
    cout << "K-th smallest element:- ";
    cout << ans << endl;
}

You can also try this code with Online C++ Compiler

Run Code

Output- 

K-th smallest element:- 5

Complexity Analysis

The time complexity for this approach is - O(nlogK)

The space complexity for this approach will be - O(K) max heap hold at max K element.

Also Read, Prefix Sum Array

Read about Application of Queue in Data Structure here.