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

Ayush Tiwari
Last Updated: May 13, 2022

Introduction

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

E.g:

Input: 

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

Output: 

7

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 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;
}

 

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.

Frequently asked questions

1. What is a Priority Queue?

Ans. This is the implementation of the heap in which the root element is a higher priority in the form of maximum or minimum.

 

2. How do we declare min heap in c++?

Ans.

priority_queue< data_type, vector<data_type>, greater<data_type>> variable_name 

 

3. Write applications of Priority Queue.

Ans. Application of priority queue are as follows:-

   1. Some algorithms like Dijkstra’s shortest path algorithm, Prim’s Minimum Spanning Tree, etc

   2. CPU scheduling in the operating system.

   3. Sorting algorithm like heap-sort.

Key takeaways

In this blog, we learned about them, methods we can use to find the K-th smallest element in an unsorted array using a priority queue.

We hope you gained some insight into this problem, and now it is your turn to practice this problem and code it out in your way.

Don’t Stop here; try more problems in the linked list and gain expertise!

1. Array-Rotation

2. Multi-Dimensional-arrays

Keep Learning, Keep Going.

Happy Coding!

You can learn more about the priority queue here. Also, don’t forget to practice similar problems on Code studio.

Was this article helpful ?
0 upvotes