Introduction
Finding the Kth largest or Kth smallest element in an array is a common problem in computer science. Given an unsorted array of size n and an integer k, we have to find the Kth largest or Kth smallest element in the array. There are several approaches to solve this problem, including the brute force approach, the Quickselect algorithm, and the Priority Queue approach with a Heap.
In this blog post, we will focus on the Priority Queue approach with a Heap to find the Kth largest or Kth smallest element in an array. We will discuss how to implement this approach using a Max Heap to find the Kth largest element, and using a Min Heap to find the Kth smallest element.
Problem Definition
Given an unsorted array arr of size n and an integer k, we have to find the Kth largest or Kth smallest element in the array.
Brute Force Solution
A brute force solution to find the Kth largest or Kth smallest element in an array is to sort the array in ascending or descending order and then return the Kth element.
Sorting the array can be done using various sorting algorithms, such as Merge Sort, Quick Sort, or Heap Sort. However, the time complexity of these sorting algorithms is O(n log n), which might not be efficient for larger arrays.
Priority Queue Approach with a Heap
The Priority Queue approach with a Heap is a more efficient solution to find the Kth largest or Kth smallest element in an array. This approach uses a Heap data structure to keep track of the K largest or K smallest elements in the array.
To find the Kth largest element in an array using a Priority Queue with a Max Heap, we can create a Max Heap with the first k elements of the array. Then, we can iterate over the remaining elements of the array, and for each element, we compare it with the root of the Max Heap. If the element is greater than the root, we replace the root with the element and heapify the Max Heap. At the end of the iteration, the root of the Max Heap will be the Kth largest element in the array.
To find the Kth smallest element in an array using a Priority Queue with a Min Heap, we can create a Min Heap with the first k elements of the array. Then, we can iterate over the remaining elements of the array, and for each element, we compare it with the root of the Min Heap. If the element is less than the root, we replace the root with the element and heapify the Min Heap. At the end of the iteration, the root of the Min Heap will be the Kth smallest element in the array.
Algorithm & Pseudo Code for Kth largest with Max Heap
Algorithm
Algorithm for Kth largest element with Max Heap
Create a Max Heap with the first k elements of the array.
For each remaining element num in the array:
If num is greater than the root of the Max Heap, replace the root with num and heapify the Max Heap.
Return the root of the Max Heap.
Pseudo Code
Pseudo Code for finding the Kth largest element using a Max Heap
function findKthLargest(arr, k):
maxHeap = new MaxHeap(arr[0:k])
for i = k+1 to n:
if arr[i] > maxHeap.root:
maxHeap.replaceRoot(arr[i])
return maxHeap.root
Algorithm & Pseudo Code for Kth smallest with Min Heap
Algorithm
Create a Min Heap with the first k elements of the array.
For each remaining element num in the array:
If num is less than the root of the Min Heap, replace the root with num and heapify the Min Heap.
Return the root of the Min Heap.
Pseudo Code
Pseudo Code for finding the Kth smallest element using a Min Heap
function findKthSmallest(arr, k):
minHeap = new MinHeap(arr[0:k])
for i = k+1 to n:
if arr[i] < minHeap.root:
minHeap.replaceRoot(arr[i])
return minHeap.root
Example Code in C++
Here is the C++ implementation of the Priority Queue approach with a Heap to find the Kth largest or Kth smallest element in an array:
#include <vector>
#include <queue>
using namespace std;
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> maxHeap;
for(int i = 0; i < nums.size(); i++){
if(i < k){
maxHeap.push(nums[i]);
}else{
if(nums[i] < maxHeap.top()){
maxHeap.pop();
maxHeap.push(nums[i]);
}
}
}
return maxHeap.top();
}
int findKthSmallest(vector<int>& nums, int k) {
priority_queue<int, vector<int>, greater<int>> minHeap;
for(int i = 0; i < nums.size(); i++){
if(i < k){
minHeap.push(nums[i]);
}else{
if(nums[i] > minHeap.top()){
minHeap.pop();
minHeap.push(nums[i]);
}
}
}
return minHeap.top();
}
int main() {
vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
int k = 4;
int kthLargest = findKthLargest(nums, k);
int kthSmallest = findKthSmallest(nums, k);
cout << "The " << k << "th largest element is " << kthLargest << endl;
cout << "The " << k << "th smallest element is " << kthSmallest << endl;
return 0;
}
Time and Space Complexity Analysis
The time complexity of the Priority Queue approach with a Heap to find the Kth largest or Kth smallest element in an array is O(n log k), where n is the size of the array and k is the value of k.
This is because we need to iterate over the array once, and for each element, we perform a heapify operation that takes O(log k) time.
The space complexity of the approach is O(k), which is the size of the heap we create.