An Overview of 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 uses 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-genericpriority 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 fixedsize in Java. Our solution to 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.

package priorityqueue;

public class PriorityQueue {

    private int[] innerArray;
    private int size;

    public PriorityQueue() {
        this.innerArray = new int[10];
        size = 0;
    }

    public void enqueue(int x) {

    }

    public int dequeue() {
        return 0;
    }

    public int peek() {
        return 0;
    }

    public boolean contains(int x) {
        return false;
    }

    public boolean isEmpty() {
        return false;
    }

    public int size() {
        return 0;
    }

    private void doubleArray() {

    }
}

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, and 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.

public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

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.

public int peek() {
        if (isEmpty())
            throw new NoSuchElementException("The queue is empty");
        return innerArray[0];
    }

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.

In other words: We'll get a false positive.

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

public boolean contains(int x) {
        // Check for empty.
        if(isEmpty())
            return false;
        // Looping through the positions which contains inserted values,
        // ignoring trailing default 0 values.
        for(int i = 0; i < size; i++) {
            // Comparing
            if(innerArray[i] == x)
                return true;
        }

        // None found
        return false;
    }

Implementing Enqueue and 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 its 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.

public void enqueue(int x) {
        // If it is empty, insert in front
        if (size == 0) {
            size++;
            innerArray[0] = x;
            return;
        }

        // If full, we'll have to double the array
        if (size() == innerArray.length)
            doubleArray();

        // Looping through
        int temp = x;
        for (int i = 0; i < size; i++) {
            // If priority is higher, ie. values is lower, we shift.
            if (x <= innerArray[i]) {
                int next;
                temp = innerArray[i];
                innerArray[i] = x;
                // Shifting
                while (i < size - 1) {
                    next = innerArray[i + 1];
                    innerArray[i + 1] = temp;
                    temp = next;
                    i++;
                }
                break;
            }
        }

        // Placing, increasing size.
        innerArray[size] = temp;
        size++;
    }

 Dequeueworks very much in the same way.

public int dequeue() {
        // NoSuchElement
        if (isEmpty())
            throw new NoSuchElementException("The queue is empty");

        // Storing first int for return
        int retValue = innerArray[0];
        // Shifting all values downwards
        for (int i = 1; i < size; i++) {
            innerArray[i - 1] = innerArray[i];
        }

        innerArray[size - 1] = 0;
        size--;
        return retValue;
    }

Implementing doubleArray

All that's left now is to implement the method that doubles 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.

private void doubleArray() {
        int[] newArr = new int[innerArray.length * 2];

        for(int i = 0; i < innerArray.length; i++) {
            newArr[i] = innerArray[i];
        }

        innerArray = newArr;
    }

Complete Implementation

The complete implementation can be found below. Happy coding!

package priorityqueue;

import java.util.NoSuchElementException;

public class PriorityQueue {

    private int[] innerArray;
    private int size;

    public PriorityQueue() {
        this.innerArray = new int[10];
        size = 0;
    }

    public void enqueue(int x) {
        // If it is empty, insert in front
        if (size == 0) {
            size++;
            innerArray[0] = x;
            return;
        }

        // If full, we'll have to double the array
        if (size() == innerArray.length)
            doubleArray();

        // Looping through
        int temp = x;
        for (int i = 0; i < size; i++) {
            // If priority is higher, ie. values is lower, we shift.
            if (x <= innerArray[i]) {
                int next;
                temp = innerArray[i];
                innerArray[i] = x;
                // Shifting
                while (i < size - 1) {
                    next = innerArray[i + 1];
                    innerArray[i + 1] = temp;
                    temp = next;
                    i++;
                }
                break;
            }
        }

        // Placing, increasing size.
        innerArray[size] = temp;
        size++;
    }

    public int dequeue() {
        // NoSuchElement
        if (isEmpty())
            throw new NoSuchElementException("The queue is empty");

        // Storing first int for return
        int retValue = innerArray[0];
        // Shifting all values downwards
        for (int i = 1; i < size; i++) {
            innerArray[i - 1] = innerArray[i];
        }

        innerArray[size - 1] = 0;
        size--;
        return retValue;
    }

    public int peek() {
        if (isEmpty())
            throw new NoSuchElementException("The queue is empty");
        return innerArray[0];
    }

    public boolean contains(int x) {
        // Check for empty.
        if (isEmpty())
            return false;
        // Looping through the positions which contains inserted values,
        // ignoring trailing default 0 values.
        for (int i = 0; i < size; i++) {
            // Comparing
            if (innerArray[i] == x)
                return true;
        }

        // None found
        return false;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int size() {
        return size;
    }

    private void doubleArray() {
        int[] newArr = new int[innerArray.length * 2];

        for(int i = 0; i < innerArray.length; i++) {
            newArr[i] = innerArray[i];
        }

        innerArray = newArr;
    }
}