Priority Queue in Java. Quick Tutorial with Examples

PriorityQueue is a very useful built-in collection that all Java developers should be familiar with. Once you learn it, you’ll have another tool in your toolkit to build efficient applications. When learning priority queues, it’s important to learn the underlying concepts which are pretty straight-forward and will help you make design decisions wisely. In this tutorial, I’m going to show you what a priority queue is, important concepts, high-level overview of internals and finish it all of with a complete working Java program. Without further ado, let’s start.

What is a Priority Queue?

Let’s do a quick recap. A queue is an efficient data-structure (collection) for storing a number of objects. The objects can be added in any arbitrary order and the queue remembers and keeps the order in which they were added. It supports retrieving elements only from its head or tail, which means you can only remove by the very first element you inserted into the queue (or the very last one.) Queues are often used to distribute work to a pool of workers. They act as a buffer between producers who are producing work at a high rate, and a limited pool of workers who are carrying out the work. For example, ThreadPool library in Java uses a queue to hold tasks submitted to it and transfers them to worker threads when they become available.

In many use cases, the default order of the queue (first-in-first-out) is sufficient. If you’re submitting jobs or tasks to a ThreadPool that are all the same, it is often desirable to process them in the same order in which they were submitted. But there are times when you’d want to process a category of high-priority tasks before low-priority ones. Suppose, you’re receiving online orders from your users and storing them in a queue to be processed by available workers. With a vanilla queue, the orders will be processed in the order in which they arrived. Now imagine that you want to expedite orders from premium customers and process them first over regular customers. Thanks to priority queues, you’re saved from doing extra work of implementing logic to handle priorities elsewhere in your code.

Priority queues are designed to support insertion in any arbitrary order, but retrieval in a sorted manner as defined by users. To store elements, a priority queue uses a data structure called binary heap. A binary heap is a self-organizing binary tree which adjusts itself each time elements are added or removed from it. In the case of min-heap, the smallest element (1) is always kept at the very top regardless of the order in which it was inserted.

Min_Heap

It is important to call out that priority queues (binary heaps) do not store elements in absolute sorted order necessarily. It imposes semi-ordering for efficiency in terms of speed of insertion and retrieval. I’ll show this with an example by iterating through a priority queue.

Priority Queues in Java

A PriorityQueue is a type of queue which allows Java developers to insert elements in arbitrary order but retrieve them in a specific (sorted) order. The elements of the priority queue are ordered using a Comparator provided when the queue was created. Let’s look at a complete example.

package com.codeahoy.tutorial.datastructures;

import java.util.PriorityQueue;

public class PriorityQueueExample {

    public static void main(String[] args) {

        // Create a PriorityQueue that sorts elements
        // by their natural ordering
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // Let's add some elements to the PriorityQueue
        Integer [] elements = new Integer[]{8, 100, 98, 10, 2,
                15, 45, 25, 76, 3, 9, 1, 63, };

        for (int e: elements) {
            pq.add(e);
        }

        // Let's iterate through the elements to see they
        // are not necessarily stored in sorted order
        System.out.print("Print by Iterating: ");
        for(int e: pq) {
            System.out.print(e + " ");
        }

        System.out.println();
        System.out.print("Print by Retrieval: ");

        // Let's remove elements one by one
        while (!pq.isEmpty()) {
            System.out.print(pq.remove() + " ");
        }
    }
}

Output

Print by Iterating: 1 3 2 25 8 15 45 100 76 10 9 98 63 
Print by Retrieval: 1 2 3 8 9 10 15 25 45 63 76 98 100 

In the example above, you can see that I added a few integers to the queue in arbitrary order. Then I iterated through the queue and printed the elements. Here you can see that the elements are not stored in a sorted order. This is because binary heap only guarantees semi-ordering as discussed above: elements in the higher nodes are greater (or less) than than the elements in lower nodes. For example in a max-heap, parents are always greater than their children, as can be seen in the image below. Unlike Binary Search Trees, heaps don’t maintains absolute left-to-right ordering.

Max_Heap

PriorityBlocking Queue

PriorityBlockingQueue is a cousin of PriorityQueue in Java. It supports all the features of PriorityQueue and adds support for blocking operations. A blocking queue allow workers to ‘block’ or ‘wait’ if the queue is empty. They remain in the blocked state until new tasks arrive. Blocking queues are very convenient when building worker pools and are widely used by developers.

That’s all! In this post, we learned about priority queues and binary heap which it uses under the hood. If you need a refresher or more in-depth look at the heap data structure, I highly recommend that you watch the following video which does a pretty good job of covering this topic.

Image credits: By Ermishin - Own work, CC BY-SA 3.0, https://commons.wikimedia.org/w/index.php?curid=12251273

Please leave your comments below and like on Facebook or follow on Twitter to stay up-to-date.

comments powered by Disqus