Priority Queue

Priority queue is a data structure that supports at least the following operations:

1. Insert an element in the queue in O(logN) time (where N is the size of the queue).
2. Find the largest (or the smallest) element in the queue in O(1) time.
3. Remove an element from the queue in O(logN) time.

Most languages have built-in priority queue libraries:

PriorityQueue<Integer> queue = new PriorityQueue<>();
      
queue.add(2);
queue.add(3);
queue.add(8);

// queue.peek() finds the minimum element in the queue.
System.out.println(queue.peek()); // prints 2.

queue.poll();                     // queue.poll() removes the minimum element from the queue.
System.out.println(queue.peek()); // prints 3 now.

queue.add(-7);
System.out.println(queue.peek()); // prints -7

As you can see, in Java priority queue is maintaining minimum element by default, and in C++ it's maintaining maximum. You can easily reverse it in both languages:

PriorityQueue<Integer> queue = new PriorityQueue<>((a, b) -> b - a);
        
queue.add(2);
queue.add(3);
queue.add(8);

// queue.peek() now finds the maximum element in the queue.
System.out.println(queue.peek()); // prints 8.

queue.poll();                     // queue.poll() also removes the maximum element now.
System.out.println(queue.peek()); // prints 3 now.

queue.add(-7);
System.out.println(queue.peek()); // prints 3 again.

In fact, you can use any comparator in the priority queue – look up how to do it in your favourite language.

Problems

So, when do you need a priority queue? It comes handy when you need to maintain the minimum in the collection of elements, and you always remove only the smallest element as well (from now on, I will always say minimum, but the same can apply to the maximum as well).

For example, you can solve the following problem with priority queue. Can you do it in O(NlogK) time?

The following problem can be solved with a smart application of priority queues. Can you solve it?

Diving deeper

If you want to learn more about priority queues, it's a good idea to learn how they are implemented – it's actually not that hard. You can read that in Introduction to Algorithms (also read there about heaps, an alternative name for the priority queues), in Wikipedia, or in many other online sources that you can google up.

Understanding how priority queues / heaps work, and writing one from scratch is a great exercise. Also, try to learn the following: how to build a priority queue with N elements in O(N) time?

More practice problems

Here are some more good problems that can be solved with priority queues: