Priority Queue vs Sorting

What is sorting?

Sorting is an approach/algorithm which puts data in a meaningful order. The most common ordering is increasing or decreasing. In programming, we generally have an array on size n which we can sort in any order. There are multiple algorithms for sorting and the best average case time complexity is O(n log n).

What is a priority queue?

A priority queue is an abstract data type that behaves similarly to the normal queue except that each element has some priority, i.e., the element with the highest priority would come first in a priority queue. The priority of the elements in a priority queue will determine the order in which elements are removed from the priority queue.

The priority queue supports only comparable elements, which means that the elements are either arranged in an ascending or descending order.

Implementation?

The priority queue internally uses a heap to keep elements in the right order. You can refer to this link to learn more about how heap sort can be implemented. We will focus on what APIs and classes you can use to implement a priority queue in your code. We are using Java in this example.

How to create a priority queue?

// Integer is object type
PriorityQueue<Integer> pq = new PriorityQueue<>();

How to add a new element?

pq.add(6);

Time complexity: O(log n), where n is the number of elements in the pq

How to check the top element?

int element = pq.peek();

Time complexity: O(1)

How to remove the top element?

pq.poll();

Time complexity: O(log n), where n is the number of elements in the pq.

We have used an Integer type here but it can be any custom object as well. The only condition it needs to follow is that it should be comparable. If it’s a custom object, you need to implement a comparable interface in the custom…