K-th Smallest Element in an Unsorted Array using Priority Queue
Given an array arr[] consisting of N integers and an integer K, the task is to find the Kth smallest element in the array using Priority Queue.
Examples:
Input: arr[] = {5, 20, 10, 7, 1}, N = 5, K = 2
Output: 5
Explanation: In the given array, the 2nd smallest element is 5. Therefore, the required output is 5.Input: arr[] = {5, 20, 10, 7, 1}, N = 5, K = 5
Output: 20
Explanation: In the given array, the 5th smallest element is 20. Therefore, the required output is 20.
Approach: The idea is to use PriorityQueue Collection in Java or priority_queue STL library to implement Max_Heap to find the Kth smallest array element. Follow the steps below to solve the problem:
- Implement Max Heap using a priority_queue.
- Push first K array elements into the priority_queue.
- From there on, after every insertion of an array element, pop the element at the top of the priority_queue.
- After complete traversal of the array, print the element at the top of the priority queue as the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to find kth smallest array element void kthSmallest(vector< int >& v, int N, int K) { // Implement Max Heap using // a Priority Queue priority_queue< int > heap1; for ( int i = 0; i < N; ++i) { // Insert elements into // the priority queue heap1.push(v[i]); // If size of the priority // queue exceeds k if (heap1.size() > K) { heap1.pop(); } } // Print the k-th smallest element cout << heap1.top() << endl; } // Driver code int main() { // Given array vector< int > vec = { 5, 20, 10, 7, 1 }; // Size of array int N = vec.size(); // Given K int K = 2; // Function Call kthSmallest(vec, N, K % (N+1)); return 0; } |
Java
// Java program for the above approach import java.util.*; class CustomComparator implements Comparator<Integer> { @Override public int compare(Integer number1, Integer number2) { int value = number1.compareTo(number2); // elements are sorted in reverse order if (value > 0 ) { return - 1 ; } else if (value < 0 ) { return 1 ; } else { return 0 ; } } } class GFG{ // Function to find kth smallest array element static void kthSmallest( int []v, int N, int K) { // Implement Max Heap using // a Priority Queue PriorityQueue<Integer> heap1 = new PriorityQueue<Integer>( new CustomComparator()); for ( int i = 0 ; i < N; ++i) { // Insert elements into // the priority queue heap1.add(v[i]); // If size of the priority // queue exceeds k if (heap1.size() > K) { heap1.remove(); } } // Print the k-th smallest element System.out.print(heap1.peek() + "\n" ); } // Driver code public static void main(String[] args) { // Given array int []vec = { 5 , 20 , 10 , 7 , 1 }; // Size of array int N = vec.length; // Given K int K = 2 ; // Function Call kthSmallest(vec, N, K % N); } } // This code is contributed by Amit Katiyar |
Python3
# Python3 program for the above approach # Function to find kth smallest array element def kthSmallest(v, N, K): # Implement Max Heap using # a Priority Queue heap1 = [] for i in range (N): # Insert elements into # the priority queue heap1.append(v[i]) # If size of the priority # queue exceeds k if ( len (heap1) > K): heap1.sort() heap1.reverse() del heap1[ 0 ] # Print the k-th smallest element heap1.sort() heap1.reverse() print (heap1[ 0 ]) # Driver code # Given array vec = [ 5 , 20 , 10 , 7 , 1 ] # Size of array N = len (vec) # Given K K = 2 # Function Call kthSmallest(vec, N, K % N) # This code is contributed by divyeshrabadiya07 |
C#
// C# program for the above approach using System; using System.Collections.Generic; class GFG { // Function to find kth smallest array element static void kthSmallest( int []v, int N, int K) { // Implement Max Heap using // a Priority Queue List< int > heap1 = new List< int >(); for ( int i = 0; i < N; ++i) { // Insert elements into // the priority queue heap1.Add(v[i]); // If size of the priority // queue exceeds k if (heap1.Count > K) { heap1.Sort(); heap1.Reverse(); heap1.RemoveAt(0); } } heap1.Sort(); heap1.Reverse(); // Print the k-th smallest element Console.WriteLine(heap1[0]); } // Driver code public static void Main(String[] args) { // Given array int []vec = { 5, 20, 10, 7, 1 }; // Size of array int N = vec.Length; // Given K int K = 2; // Function Call kthSmallest(vec, N, K % N); } } // This code is contributed by gauravrajput1 |
Javascript
<script> // Javascript program for the above approach // Function to find kth smallest array element function kthSmallest(v,N,K) { let heap1 = []; for (let i = 0; i < N; ++i) { // Insert elements into // the priority queue heap1.push(v[i]); // If size of the priority // queue exceeds k if (heap1.length > K) { heap1.sort( function (a,b){ return a-b; }); heap1.reverse(); heap1.shift(); } } heap1.sort( function (a,b){ return a-b; }); heap1.reverse(); // Print the k-th smallest element document.write(heap1[0] + "<br>" ); } // Driver code // Given array let vec=[5, 20, 10, 7, 1 ]; // Size of array let N = vec.length; // Given K let K = 2; // Function Call kthSmallest(vec, N, K % N); // This code is contributed by patel2127 </script> |
5
Time Complexity: O(N LogK)
Auxiliary Space: O(K), since the priority queue at any time holds at max k elements.