Implementing a Priority Queue Using a Heap

In the last part of the tutorial series, we implemented a queue using an array. In this final part of the series, I will show you how to implement a priority queue using a heap.

As a reminder: In a priority queue, the elements are not retrieved in FIFO order but according to their priority. The highest priority element is always at the head of the queue and is taken first – regardless of when it was inserted into the queue.

What Is a Heap?

A "heap" is a binary tree in which each node is either greater than or equal to its children ("max heap") – or less than or equal to its children ("min-heap").

For the priority queue in this article, we use a min heap because the highest priority is the one with the lowest number (priority 1 is usually higher than priority 2).

Here is an example of what such a min-heap might look like:

The element at each node of this tree is less than the elements of its two child nodes:

• 1 is less than 2 and 4;
• 2 is less than 3 and 7;
• 4 is less than 9 and 6;
• 3 is less than 8 and 5.

Array Representation of a Heap

We can store a heap in an array by mapping its elements row by row – from top left to bottom right – to the array:

Our example heap looks like this as an array:

In a min-heap, the smallest element is always at the top, i.e., in the array, it is always at the first position. This is why, when you print a Java PriorityQueue as a string, you see the smallest element on the left. What you see is the array representation of the min-heap underlying the PriorityQueue.

The following lines of code demonstrate this well:

PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
priorityQueue.addAll(List.of(4, 7, 3, 8, 2, 9, 6, 5, 1));
System.out.println("priorityQueue = " + priorityQueue);Code language: Java (java)

The output of the program is:

priorityQueue = [1, 2, 4, 3, 7, 9, 6, 8, 5]Code language: plaintext (plaintext)

The smallest element is on the far left. And if you look closely, you'll see that the numbers are in the same order as in the graphical array representation above. The min-heap of the PriorityQueue created in the example is precisely the one I displayed at the beginning of the article.

Priority Queue Using a Min-Heap – The Algorithm

OK, the smallest element is always on the left. That tells how the peek() operation has to work: it simply has to return the first element of the array.

But how is such a heap constructed? How do enqueue() and dequeue() work?

Inserting into the Min-Heap: Sift Up

To insert an element into a heap, we proceed as follows:

1. We insert the new element as the last element in the tree, i.e.:
   • If the tree is empty, we insert the new element as the root.
   • If the lowest level of the tree is not complete, we insert the new element next to the last node of the lowest level.
   • If the lowest level is complete, we append the node under the first node of the lowest level.
2. As long as the parent node of the new element is less than the element itself (which would violate the min-heap rule), we swap the new node with its parent node.

Step 1 sounds complicated, but in the array representation, it simply means that the new element is placed in the first free position of the array. Step 2 ensures that, at the end of the operation, each element is again less than its children.

The example in the following section demonstrates the two steps.

Inserting into the Min-Heap: Example

In the following examples, I will show you step by step how to fill a min-heap-based priority queue with the sample values shown above (4, 7, 3, 8, 2, 9, 6, 5, 1). I'll show the min-heap in its tree and array representations in each step.

1^st Element – Inserting the 4 into an Empty Priority Queue

The first element to be inserted becomes the root node of the tree; in the array, we place it at the first position:

2^nd Element – Inserting the 7

We append the 7 below the first node of the lowest level – that is, below the root on the left. In the array, we simply append it:

The 7 is greater than its parent node 4 – thus, the insertion operation is complete. The smallest element is still at the beginning of the priority queue.

3^rd Element - Inserting the 3

We append the 3 next to the last node of the lowest level, that is, as right child of the 4. In the array, it comes at the end:

The 3 is less than its parent node. The min-heap rules are, therefore, violated. We restore the min-heap by swapping the 3 with the 4:

We now have a valid min-heap again.

We skip 8, 2, 9, 6, and 5 (these are inserted analogously) and come to the…

9^th Element – Inserting the 1

Finally, we add the 1 to the end of the queue (and the array):

The 1 is greater than its parent node 5; thus, our tree is no longer a valid min-heap. To fix it, we first swap the 1 with the 5:

The 1 is also greater than its new parent node 3; thus, we swap again:

The 1 is also greater than the root 2, so we swap a third time:

Since the 1 has now reached the root, the operation is finished. The tree is again a min-heap. The smallest element is at the tree's root (and at the beginning of the array).

This reaching up of the inserted element in the way just shown is called "sift up".

Simplified Sift Up Algorithm

In fact, we don't even need to bother inserting the new element at the end, then swapping it with its parent node step by step. Instead, we can remember the new element, move the greater parent elements down, and finally place the new element directly at its target position.

The following graphics show the insertion of the 1 according to the simplified algorithm.

The 1 is less than the empty node's parent, the 5. We, therefore, move the 5 to the free node:

The 1 is also less than the 3; we move the 3 down:

The 1 is less than the 2; we also push the 2 down:

We can't move any more elements down, so we put the element to be inserted, the 1, on the now-vacated root node (or the first field in the array):

This completes the sift up operation.

Inserting an element into the priority queue (or min-heap) may seem very complex the first time you read through it. If you don't understand it, take a break and repeat the chapter before proceeding to the dequeue operation.

Removing from the Min-Heap: Sift Down

We know that the smallest element is always at the tree's root (or at the beginning of the array).

To remove it, we proceed as follows:

1. We remove the root element from the tree.
2. We move the last node of the lowest level of the tree (which corresponds to the last field of the array) to the vacated root position.
3. As long as this node is greater than one of its children (which would violate the min-heap rule), we swap the node with its smallest child node.

Removing from the Min-Heap: Example

The following example shows how we remove the root element of the min-heap filled in the last chapter – and then restore the min-heap condition.

The first thing we do is take out the root element:

Second, we move the tree's last element, the 5, to the now-vacated root node:

Since the new root element, 5, is greater than the smallest of its children, 2, we swap those two elements:

The 5 is still greater than the smallest of its children, the 3. We swap a second time:

The 5 is now greater than its only child; we have thus restored the min-heap condition.

The root of the min-heap (the first field of the array) now contains the 2, the new smallest element after removing the 1.

The reaching down of the element moved to the root is called "sift down".

Simplified Sift Down Algorithm

We can also simplify the sift down algorithm. We don't have to move the last element (the 5 in the example) to the root first and then gradually swap it with its children. We can instead move the greater elements up first and, in the end, move the last element directly to its final position.

The following illustrations show the passing down of the 5 (or rather: the free field on which the 5 is placed in the end) according to the simplified algorithm.

The 5 is greater than the smallest child node of the empty root, the 2. We move the 2 up:

The 5 is also greater than the smallest child of the now-vacant node, the 3. We also move the 3 up:

The 5 is not greater than the only child of the now-vacant node, the 8. So we have found the target node for the 5, and we push the 5 there:

We have restored the min-heap condition.

The sift up and sift down operations may seem complex, but we can implement them both in 10 lines of Java code or less. You'll learn how in the next chapter.

Source Code for Priority Queue with Min-Heap

The following source code shows how to implement a priority queue with a min-heap (class HeapPriorityQueue in the GitHub repository). Due to the length of the class, I am going to divide it into sections.

Constructors

There are two constructors: one where you can specify the initial size of the array and a default constructor that sets the initial capacity to ten:

public class HeapPriorityQueue<E extends Comparable<? super E>> implements Queue<E> {

  private static final int DEFAULT_INITIAL_CAPACITY = 10;
  private static final int ROOT_INDEX = 0;

  private Object[] elements;
  private int numberOfElements;

  public HeapPriorityQueue() {
    this(DEFAULT_INITIAL_CAPACITY);
  }

  public HeapPriorityQueue(int capacity) {
    if (capacity < 1) {
      throw new IllegalArgumentException("Capacity must be 1 or higher");
    }

    elements = new Object[capacity];
  }
Code language: Java (java)

enqueue()

The enqueue() method first checks if the queue is full. If it is, it calls the grow() method, which copies the array into a new, larger array:

  @Override
  public void enqueue(E newElement) {
    if (numberOfElements == elements.length) {
      grow();
    }
    siftUp(newElement);
    numberOfElements++;
  }

  private void grow() {
    int newCapacity = elements.length + elements.length / 2;
    elements = Arrays.copyOf(elements, newCapacity);
  }Code language: Java (java)

I have depicted the grow() method in a very simplified way here since the focus should be on the siftUp() and siftDown() methods.

In the HeapPriorityQueue class in the GitHub repository, the grow() method increases the array by factor 2 up to a specific size (64 elements) and, after that, by factor 1.5. It also ensures that we don't exceed a certain maximum size.

When we are sure that the array is large enough, we call the siftUp() method:

siftUp()

  private void siftUp(E newElement) {
    int insertIndex = numberOfElements;

    while (isNotRoot(insertIndex) && isParentGreater(insertIndex, newElement)) {
      copyParentDownTo(insertIndex);
      insertIndex = parentOf(insertIndex);
    }

    elements[insertIndex] = newElement;
  }

  private boolean isNotRoot(int index) {
    return index != ROOT_INDEX;
  }

  private boolean isParentGreater(int insertIndex, E element) {
    int parentIndex = parentOf(insertIndex);
    E parent = elementAt(parentIndex);
    return parent.compareTo(element) > 0;
  }

  private void copyParentDownTo(int insertIndex) {
    int parentIndex = parentOf(insertIndex);
    elements[insertIndex] = elements[parentIndex];
  }

  private int parentOf(int index) {
    return (index - 1) / 2;
  }
Code language: Java (java)

Note that I tried to implement the algorithm as readable as possible (and not as performant as possible). The parentOf() method is called three times in each iteration: once by isParentGreater(), once by copyParentDownTo() and once directly.

An optimized variant (OptimizedHeapPriorityQueue class in the GitHub repo, starting at line 74) shows a tweaked algorithm that calculates the parent index only once.

dequeue()

The dequeue() method retrieves the header element, removes the last element, and then calls siftDown(), which ultimately moves this last element to its new position.

  @Override
  public E dequeue() {
    E result = elementAtHead();
    E lastElement = removeLastElement();
    siftDown(lastElement);
    return result;
  }

  private E removeLastElement() {
    numberOfElements--;
    E lastElement = elementAt(numberOfElements);
    elements[numberOfElements] = null;
    return lastElement;
  }
Code language: Java (java)

siftDown()

siftDown() is the most complex method because it always has to compare a node with possibly two child nodes.

  private void siftDown(E lastElement) {
    int lastElementInsertIndex = ROOT_INDEX;
    while (isGreaterThanAnyChild(lastElement, lastElementInsertIndex)) {
      moveSmallestChildUpTo(lastElementInsertIndex);
      lastElementInsertIndex = smallestChildOf(lastElementInsertIndex);
    }

    elements[lastElementInsertIndex] = lastElement;
  }

  private boolean isGreaterThanAnyChild(E element, int parentIndex) {
    E leftChild = leftChildOf(parentIndex);
    E rightChild = rightChildOf(parentIndex);

    return leftChild != null && element.compareTo(leftChild) > 0
        || rightChild != null && element.compareTo(rightChild) > 0;
  }

  private E leftChildOf(int parentIndex) {
    int leftChildIndex = leftChildIndexOf(parentIndex);
    return exists(leftChildIndex) ? elementAt(leftChildIndex) : null;
  }

  private int leftChildIndexOf(int parentIndex) {
    return 2 * parentIndex + 1;
  }

  private E rightChildOf(int parentIndex) {
    int rightChildIndex = rightChildIndexOf(parentIndex);
    return exists(rightChildIndex) ? elementAt(rightChildIndex) : null;
  }

  private int rightChildIndexOf(int parentIndex) {
    return 2 * parentIndex + 2;
  }

  private boolean exists(int index) {
    return index < numberOfElements;
  }

  private void moveSmallestChildUpTo(int parentIndex) {
    int smallestChildIndex = smallestChildOf(parentIndex);
    elements[parentIndex] = elements[smallestChildIndex];
  }

  private int smallestChildOf(int parentIndex) {
    int leftChildIndex = leftChildIndexOf(parentIndex);
    int rightChildIndex = rightChildIndexOf(parentIndex);

    if (!exists(rightChildIndex)) {
      return leftChildIndex;
    }

    return smallerOf(leftChildIndex, rightChildIndex);
  }

  private int smallerOf(int leftChildIndex, int rightChildIndex) {
    E leftChild = elementAt(leftChildIndex);
    E rightChild = elementAt(rightChildIndex);
    return leftChild.compareTo(rightChild) < 0 ? leftChildIndex : rightChildIndex;
  }
Code language: Java (java)

Just like siftUp(), I wrote siftDown() with focus on readability, not on performance. Thus the positions of the child elements are calculated three times per iteration: in isGreaterThanAnyChild(), in moveSmallestChildUpTo() and again in smallestChildOf().

In the optimized class OptimizedHeapPriorityQueue, these positions are calculated only once. However, this also makes the code less easy to read.

peek(), isEmpty(), and Two Helper Methods

And finally, here are the peek() and isEmpty() methods and two helper methods used to read the element from the head of the queue or a specific position.

Since we store the elements in an Object array, we must cast the array elements to E. In order not to distribute the casts all over the source code, I have moved the casting to a central location, the method elementAt(), and suppressed the "unchecked" warning there once.

  @Override
  public E peek() {
    return elementAtHead();
  }

  private E elementAtHead() {
    E element = elementAt(0);
    if (element == null) {
      throw new NoSuchElementException();
    }
    return element;
  }

  private E elementAt(int child) {
    @SuppressWarnings("unchecked")
    E element = (E) elements[child];
    return element;
  }

  @Override
  public boolean isEmpty() {
    return numberOfElements == 0;
  }
}Code language: Java (java)

If your head isn't spinning yet, feel free to look at the source code of the JDK's PriorityQueue class. It can sort elements not only by their natural order – but also by a comparator passed to the constructor.

Conclusion

This concludes the tutorial series about queues. In this series you learned how a queue works, what bounded and unbounded, blocking and non-blocking queues are, which queue implementations exist in the JDK and how you can implement queues yourself in different ways.

If you liked the series, please leave me a comment, or share the articles using the share buttons at the end. If you still have questions, please ask them via the comment function.

Do you want to be informed about new tutorials and articles? Then click here to sign up for the HappyCoders.eu newsletter.