Kth Smallest Element In An Unsorted Array Using Priority Queue

Last Updated on December 14, 2022 by Prepbytes

Problem Statement:

The problem statement is straightforward as we have an array of size n and we have to find the k^th smallest element in an unsorted array using priority queue.

Example:
Input: n = 5
K = 2
Array = [50, 30, 70, 80, 100]

            Output: 50 (As 50 is the second smallest element in the array)

Priority Queue:

Priority queue is an abstract data type, It is a type of queue in which each element has a priority assigned to it. The priority of the element determines the order in which elements are removed from the priority queue. In the priority queue, all the elements are arranged either in ascending order or descending order.

Priority Queue Properties:

• In the priority queue, every element has priority assigned to it.
• The element with highest priority first.
• If two elements are having the same priority then they are served according to their order in the queue.

Approach:

The approach is quite simple: we’ll use max-heap to find the k^th smallest element in an unsorted array.

Algorithm:

• Implement a max-heap.
• Insert first k elements of the array into the max-heap. (A[0….k-1])
• For the remaining element of the array. (A[k….n-1])
  • Insert the element one by one in a max-heap and check if the size of the max-heap is greater than k.
  • If so, pop the element from the top.
  • Repeat the above process till the array becomes empty.
• Then, return the top most element of the max-heap i.e. kth smallest element of the array.

#include 
using namespace std;

void kthSmallest(vector& v, int N, int K)
{
	priority_queue heap1;

	for (int i = 0; i < N; ++i) {

		heap1.push(v[i]);

		if (heap1.size() > K) {
			heap1.pop();
		}
	}

	cout << heap1.top() << endl;
}

int main()
{
	vector vec = { 50, 20, 100, 70, 10 };

	int N = vec.size();

	int K = 2;

	kthSmallest(vec, N, K % N);

	return 0;
}

import java.util.*;
class CustomComparator implements Comparator {

	public int compare(Integer number1, Integer number2) {
		int value = number1.compareTo(number2);
	
		if (value > 0) {
			return -1;
		}
		else if (value < 0) {
			return 1;
		}
		else {
			return 0;
		}
	}
}
class PrepBytes{

static void kthSmallest(int []v, int N, int K)
{
	PriorityQueue heap1 = new PriorityQueue(new CustomComparator());

	for (int i = 0; i < N; ++i) {

		heap1.add(v[i]);

		if (heap1.size() > K) {
			heap1.remove();
		}
	}

	System.out.print(heap1.peek() +"\n");
}

public static void main(String[] args)
{
	int []vec = { 50, 20, 100, 70, 10};

	int N = vec.length;

	int K = 2;

	kthSmallest(vec, N, K % N);
}
}

def kthSmallest(v, N, K):
	
	heap1 = []

	for i in range(N):
		
		heap1.append(v[i])

		if (len(heap1) > K):
			heap1.sort()
			heap1.reverse()
			del heap1[0]

	heap1.sort()
	heap1.reverse()
	print(heap1[0])

vec = [ 50, 20, 100, 70, 10 ]

N = len(vec)

K = 2

kthSmallest(vec, N, K % N)

This article tried to discuss the concept of Kth Smallest Element In An Unsorted Array Using Priority Queue. Hope this blog helps you understand the concept. To practice problems you can check out MYCODE | Competitive Programming – Heaps at Prepbytes