Priority Queue in 2 mins with Example

We know that QUEUE is FIFO(first in first out) data structure but if we want to give priority to our objects that is when PriorityQueue is being used.

Simple example: we have seen in most of the applications/websites classifies the users as Premium and standard customers. When customers sending request to the application if you want the premium customers request to be handled first, then PriorityQueue will be helpful.

Priority queue is based on priority heap and stored in natural order by default.
We can give a custom ordering with the help of comparator.
The head of the PriorityQueue will have minimum element based on natural or comparator based ordering.

Kth Largest element in an array is the best example of Priority Queue

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int i:nums){
            pq.add(i);
            if(pq.size()>k){
                pq.remove();
            }
        }
        return pq.peek();
    }
}

Since we know the PriorityQueue always maintains minimum element at head once we encounter any element and checks if that is smaller than the existing head element if yes the head will point to new minimum element.

The remove here will delete the minimum element which head is currently pointing to in the iteration.
ex. 3,2,1,5,6,4 and k=2
first iteration: 3 and 2<3 hence 2 will be the head
now 2,3 and 1<2 hence 1 will be head
now 1,2,3-> size>k hence remove 1 from the priority queue
so the steps follows and keep removing smallest element when size>k it get the kth largest in the array.

Thanks for reading