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 Kth smallest element in the unsorted array by using a Priority queue.
There could be many ways to find the Kth 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 Kth smallest element in the array using a datastructure 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 Maxheap to find the Kth smallest element in an unsorted array.
Algorithm
 Construct a maxheap.
 Insert the first K elements of array [0â€¦K1] into the maxheap.

Then for the remaining elements of array[kâ€¦n1],
 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 Kth smallest element.
Implementation in C++
#include <bits/stdc++.h>
using namespace std;
// Fuction to find Kth 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 Kth 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 << "Kth smallest element: ";
cout << ans << endl;
}
Output
Kth 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.