Priority Queue in Go - Part 1 of n

When learning a new language, I like to get a lot of practice. Going through examples in books or online tutorials can be helpful, I also like to do other challenges like writing implementations of common data structures and algorithms, like those you learn about when getting a computer science degree. Since I studied mechanical engineering, I didn’t get that much exposure to them while in school. I have studied them though, and implemented many common ones like linked lists, stacks and double-ended queues. One I haven’t done before, however, is the Priority Queue. Since I am learning Go, I thought I would give this a try. In this first part of the series, I am going to show the first steps of the implementation, including the tests. The goal is to get items added to a queue, and verify they are in the order I would expect them. This will make more sense when I get into the implementation.

Features of a Priority Queue

Before I get into the implementation, I will first cover what operations will need to be supported and how they will be implemented. To be a priority queue, it must support at least these operations:

• Is Empty?

• Add, which consists of a priority and the value that is being added. For example, a Job might have some priority.

• Pull, gets the item with the highest priority and removes it from the queue

As the implementation evolves, more methods will be added, in part to make it more testable.

Before even starting the implementation, I decided to implement it as a Heap. In fact, when I was looking for exercises, I was initially motivated by wanting to implement a heap, but landed on implementing a priority queue using a heap instead. Digression aside, this approach implies that items are stored in array, with the items being ordered in a manner that represents a tree.

Though not strictly necessary, the implementation will have two additional properties. First, the implementation will allow for a range of priorities with a priority of 1 being the lowest. Second, there can only be one item per priority. For example, if there maximum priority is 3, there can be a maximum of 3 items in the queue.

When items are added, they are inserted into the tree such that the item with the highest priority is at the root of the tree. The tree is then adjusted to maintain the so-called (max) heap property: For any node C, the key of its parent is greater than the key of itself. The root of the tree will have the highest priority.

For example, if we insert items with the priorities 5, 25, 1, 13, 16, 23, the tree will change as follows after each insertion.

The algorithm to insert an item can be broken down into two steps:

1. Add the new node to the “end” of the tree. That is, fill each level from left to right, if the level is full start a new level.

2. Move the node up the tree until it is less than its parent

The items are stored as an array, so the first step is simply inserting a new item after the last item of the array. The second step is accomplished by comparing the priority of the new item to its parent. If its key is greater than its parent, swap them. Keep doing this up the tree until the parent isn’t less than the item being added or the root is reached. This will be elaborated when the method to insert items is explained.

A Test For Adding Items

The first thing I did was write a test. The goal here is to verify an item can be added with a give priority. This will be verified by exposing a method to get the item at a given index.

package hyperds

import (
	"testing"
)

func TestItemCanBeAdded(t *testing.T) {
	unit := NewPriorityQueue[string](100)

	unit.Add(10, "val-10")

	if val := unit.get(0); *val != "val-10" {
		t.Errorf("Expected %s, was %s", "val-10", *val)
	}

	if unit.Size() != 1 {
		t.Error("Queue should have one item")
	}
}

This test will not compile because none of the code exists yet. The next step is thus to eliminate compile-time failures. I am going to skip to the point where just enough implementation is present so I can explain a little more about the structure.

package hyperds

type Priority uint64

type item[T any] struct {
	pri Priority
	val T
}

func (i item[T]) less(other item[T]) bool {
	return other.pri > 0 && i.pri < other.pri
}

type PriorityQueue[T comparable] struct {
	vals []item[T]
	size uint64
	max  Priority
}

func NewPriorityQueue[T comparable](max Priority) *PriorityQueue[T] {
	var result PriorityQueue[T]
	result.max = max
	result.vals = make([]item[T] max, max)
	return &result
}

func (p *PriorityQueue[T]) Add(pri Priority, val T) error {
	p.vals[p.size] = item[T]{val: val, pri: pri}
	p.upHeapify(p.size)
	p.size++
	return nil
}

func (p *PriorityQueue[T]) Size() uint64 {
	return p.size
}

func (p *PriorityQueue[T]) swap(i uint64, j uint64) {
	node := p.vals[i]
	p.vals[i] = p.vals[j]
	p.vals[j] = node
}

func (p *PriorityQueue[T]) less(i uint64, j uint64) bool {
	return p.vals[i].less(p.vals[j])
}

func (p *PriorityQueue[T]) get(i int) *T {
	return &p.vals[i+1].val
}

func (p *PriorityQueue[T]) upHeapify(i uint64) {
	idx := i
	for parent := p.getParent(idx); idx > 0 && p.less(parent, idx); parent = p.getParent(idx) {
		p.swap(idx, parent)
		idx = parent
	}
}

func (p *PriorityQueue[T]) getParent(c uint64) uint64 {
	return uint64(math.Floor(float64(c - 1/ 2.0)))
}

As mentioned, this implementation uses a max-heap. Items are stored in an array of a fixed size. The highest priority item is always the first item in the array. The Add method adds the new item after the last item in the array and then “up heapifies” the item until the heap property is satisfied. The parent can always be found at the floor((c-1) / 2) where c is the child’s index.

In the above example where items are added with the priorities 5, 25, 1, 13, 16, 23, the array will grow until it has the following order. Note the array is not perfectly ordered at this point. It is however balanced from the point of view of its tree structure.

Let’s add another test to verify the try structure.

func TestItemsAreInABinaryTree(t *testing.T) {
	unit := NewPriorityQueue[string](100)

	unit.Add(5, "val-5")
	unit.Add(25, "val-25")
	unit.Add(1, "val-1")
	unit.Add(13, "val-13")
	unit.Add(16, "val-16")
	unit.Add(23, "val-23")

	assertParentValue(t, unit, 5, "val-23")
	assertParentValue(t, unit, 4, "val-16")
	assertParentValue(t, unit, 3, "val-16")
	assertParentValue(t, unit, 2, "val-25")
	assertParentValue(t, unit, 1, "val-25")
}

func assertParentValue(t *testing.T, unit *PriorityQueue[string], i uint64, expected string) {
	if val := unit.get(unit.getParent(i)); *val != expected {
		t.Errorf("expected %s, was %s", expected, *val)
	}
}

Now that items have been added with the desired structure, the next method to implement to be considered a priority queue is to implement Pull. This will be covered in the next part of this series.