A simple priority queue implementation using generics and providing a simple constructor to define a comparator.

in_memory_priority_queue.go

package priorityqueue

import (
	"container/heap"
)

func NewPriorityQueue[T any](comparator func(*T, *T) bool) *InMemoryPriorityQueue[T] {
	queue := inMemoryPriorityQueue[*T]{
		Array:      make(Array[*T], 0),
		comparator: comparator,
	}
	priorityQueue := InMemoryPriorityQueue[T]{
		queue: &queue,
	}

	return &priorityQueue
}

type InMemoryPriorityQueue[T any] struct {
	queue *inMemoryPriorityQueue[*T]
}

// A InMemoryPriorityQueue implements heap.Interface and holds Items.
type inMemoryPriorityQueue[T any] struct {
	Array[T]
	comparator func(T, T) bool
}
type Array[T any] []T

func (pq inMemoryPriorityQueue[T]) Len() int { return len(pq.Array) }

func (pq inMemoryPriorityQueue[T]) Less(i, j int) bool {
	return pq.comparator(pq.Array[i], pq.Array[j])
}

func (pq inMemoryPriorityQueue[T]) Swap(i, j int) {
	pq.Array[i], pq.Array[j] = pq.Array[j], pq.Array[i]
}

func (pq *inMemoryPriorityQueue[T]) Push(x any) {
	item := x.(T)
	(*pq).Array = append((*pq).Array, item)
}

func (pq *inMemoryPriorityQueue[T]) Pop() any {
	old := (*pq).Array
	n := len(old)
	item := old[n-1]
	var zero T
	old[n-1] = zero // avoid memory leak
	(*pq).Array = old[0 : n-1]
	return item
}

func (i *InMemoryPriorityQueue[T]) Push(item *T) {
	heap.Push(i.queue, item)
	return
}

func (i *InMemoryPriorityQueue[T]) Pop() *T {
	if i.queue.Len() > 0 {
		return heap.Pop(i.queue).(*T)
	}
	return nil
}

in_memory_priority_queue_test.go

package priorityqueue

import (
	qt "github.com/frankban/quicktest"
	"github.com/snyk/org-persona-service/internal/utils/test"
	"testing"
)

type Thing struct {
	Number int
}

func comparator(thing1 *Thing, thing2 *Thing) bool {
	return thing1.Number < thing2.Number
}

func Test_whenSingleElement_returnsAnElement(t *testing.T) {
	c := test.NewUnitTest(t)

	queue := NewPriorityQueue[Thing](comparator)

	queue.Push(&Thing{3})

	c.Assert(*queue.Pop(), qt.DeepEquals, Thing{3})
}

func Test_whenSingleElement_returnsAnElementOnce(t *testing.T) {
	c := test.NewUnitTest(t)

	queue := NewPriorityQueue[Thing](comparator)

	queue.Push(&Thing{3})
	queue.Pop()

	c.Assert(queue.Pop(), qt.IsNil)
}

func Test_whenMultipleElements_returnsInPrioritisedOrder(t *testing.T) {
	c := test.NewUnitTest(t)

	queue := NewPriorityQueue[Thing](comparator)

	queue.Push(&Thing{3})
	queue.Push(&Thing{5})
	queue.Push(&Thing{7})
	queue.Push(&Thing{2})
	queue.Push(&Thing{1})

	c.Assert(*queue.Pop(), qt.DeepEquals, Thing{1})
	c.Assert(*queue.Pop(), qt.DeepEquals, Thing{2})
	c.Assert(*queue.Pop(), qt.DeepEquals, Thing{3})
	c.Assert(*queue.Pop(), qt.DeepEquals, Thing{5})
	c.Assert(*queue.Pop(), qt.DeepEquals, Thing{7})
}