Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Approach 
2.1.
Algorithm
2.2.
Implementation in C++
2.3.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What is a Priority Queue?
3.2.
How do we declare min heap in c++?
3.3.
Write applications of Priority Queue.
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

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

Author Ayush Tiwari
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

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

 

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is a Priority Queue?

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

How do we declare min heap in c++?

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

Write applications of Priority Queue.

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.

Conclusion

In this blog, we learned about the, and 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!

Recommended Reading:

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Cheers!

Previous article
Merge Two Sorted Arrays Using a Priority Queue
Next article
Last Element Remaining by Deleting the Two Largest Elements and Replacing them with Their Absolute Difference If They are Unequal
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass