pq

README

Priority Queue for Go

This package implements a priority queue on top of the container/heap package.

In addition to the standard Push and Pop functionality, it also provides functions to update the priority of an item and check if an item exists in the queue.

The main computation is done using the heap interface. Because a map of all items is maintained, the priority lookup is O(1) which is used for priority updates which is O(log n) (Source: jupp0r/go-priority-queue)

This package was inspired by jupp0r/go-priority-queue and the implementation example in the container/heap package. But both of them do not support generic types.

Documentation

Index

• Constants
• type PriorityQueue
  • func New[T comparable]() PriorityQueue[T]
  • func (p *PriorityQueue[T]) Contains(value T) bool
  • func (p *PriorityQueue[T]) Len() int
  • func (p *PriorityQueue[T]) Pop() (T, error)
  • func (p *PriorityQueue[T]) Push(value T, priority float64) error
  • func (p *PriorityQueue[T]) Update(value T, newPriority float64) error
• type PriorityQueueError
  • func (e PriorityQueueError) Error() string

Constants

const (
	ErrQueueEmpty   = PriorityQueueError("queue is empty")
	ErrItemNotFound = PriorityQueueError("item not found in the queue")
	ErrItemExists   = PriorityQueueError("item already exists in the queue")
)

Types

type PriorityQueue

type PriorityQueue[T comparable] struct {
	// contains filtered or unexported fields
}

func New

func New[T comparable]() PriorityQueue[T]

func (*PriorityQueue[T]) Contains

func (p *PriorityQueue[T]) Contains(value T) bool

func (*PriorityQueue[T]) Len

func (p *PriorityQueue[T]) Len() int

func (*PriorityQueue[T]) Pop

func (p *PriorityQueue[T]) Pop() (T, error)

func (*PriorityQueue[T]) Push

func (p *PriorityQueue[T]) Push(value T, priority float64) error

func (*PriorityQueue[T]) Update

func (p *PriorityQueue[T]) Update(value T, newPriority float64) error

type PriorityQueueError

type PriorityQueueError string

func (PriorityQueueError) Error

func (e PriorityQueueError) Error() string