The Priority Queue

The priority queue is a somewhat similar data structure to the queue. The difference lies in how the elements are being processed:

  • A standard queue strictly follows the FIFO (First In Last Out) principle.
  • A priority queue does not follow the FIFO principle.

In a priority queue, the elements are being removed from the queue based on their priority. This translates to the requirement that:

Every element in a priority queue must have a priority associated with it.

As you might have guessed – the element with the highest priority is removed from the queue (dequeued).

But how do should you define the priority of the elements in the queue?

Defining priorities to elements

Basically, you have two alternatives for defining priorities to the elements in the queue. You can either:

  • Order elements based on their natural ordering.
  • Order elements with a custom Comparator.

In this article we’ll focus on how to implement a Priority Queue, so for simplicity’s sake we’ll order the elements based on their natural ordering.

In our example the priority queue will be limited to int, so natural ordering is perfectly fine. However, keep in mind that this is for demonstration purposes only.
If you were to implement a priority queue in real life, you probably want to make use of generics, – or just do like any other developer, and use the built in java.util.PriorityQueue.

To keep our example implementation compliant with the Java specification, the least element is defined as the element with the highest priority.

Priority queue operations

The most basic set of operations for any implementation of a queue is:

  • enqueue – Inserting an element into the queue.
  • dequeue – Removing an element from the queue.
  • isEmpty – Returning true if the queue is empty.
  • size – Returning the size / number of elements in the queue.
  • contains – Returning true if the queue contains the given element.
  • peek – Returning the front element of the queue, without removing it.

Please note that the Java implementation of the Priority Queue use different names for the methods. In a production environment, I highly suggest that you use the default implementation of the Priority Queue, instead of “home growing” it.

Implementation of the priority queue

Now, let’s implement a non-generic priority queue in Java. We’ll implement one operation at a time, but first we have to decide which inner data structure we want to use.
An array is perfectly fine, so we’ll roll with that.

For those of you that are familiar with arrays, you probably know that arrays have a fixed size in Java. Our solution for this problem is that we’ll provide a private method double(), which “increases” the capacity of the array.

The code skeleton for the priority queue is presented below.

As you can see, we use an int array as the inner data structure, and initials it’s default size to 10 in the constructor. We also provide a private variable size to keep track of the number of elements.

Implementing size, isEmpty & peek

The implementation of the size and isEmpty methods are as easy as it gets. One thing to keep in mind: the size variable is used so we can avoid having to loop through the array and count “valid” integers. In the constructor, all indexes have been assigned an int with the value of 0.

What about peek? It is in fact quite simple as well – if the size is more than 0, we return the first element. If it is less than zero, we throw a NoSuchElementException.

Implementing contains

It’s time to implement contains – which should return true if the queue contains the provided parameter.

How should we implement this? One naive way would be to simply loop through the array, and return true if we encounter the provided int in the array.
However, this will not work! What if the user provides us with 0? As previously mentioned, the array is initially assigned ints with the default value – which is zero.
Said in other words: We’ll get a false positive.

The solution? Only loop through the indexes which we know contains inserted values.

Implementing enqueue & dequeue

First, let’s think about what we want to happen if we insert / enqueue an element. Note that we ignore the doubleArray method for now.
We want inserted elements to be placed in the queue, in the correct position according to it’s priority.


This visualization of the enqueue operation tells us that we’ll have to shift all elements of lower priority one position up in the array.

Dequeue works very much in the same way.

Implementing doubleArray

All that’s left now is to implement the method which double the array if we exceed the initial size. We simply copy the array’s content over to a new array, which is twice the size.

Complete implementation

The complete implementation can be found below. Happy coding. 🙂


You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *