pqueue

Documentation

Overview

Package pqueue provides a generic priority queue implementation based on container/heap. It supports both min-heap and max-heap configurations, with efficient operations for adding, updating, and removing items based on their priorities. The queue uses a map for O(1) lookups and supports custom comparators for flexible priority ordering.

Example usage:

pq := pqueue.New[int, int](pqueue.MinHeap)
pq.Put(1, 10) // Add item with value 1 and priority 10
item := pq.Get() // Retrieve item with minimum priority
fmt.Println(item.Value, item.Priority) // Output: 1 10

Index

• Variables
• type HeapKind
• type Item
• type PriorityQueue
  • func New[T comparable, V cmp.Ordered](kind HeapKind) *PriorityQueue[T, V]
  • func NewWith[T comparable, V cmp.Ordered](kind HeapKind, cmp cmp.Comparator[V]) *PriorityQueue[T, V]
  • func (pq *PriorityQueue[T, V]) Clear()
  • func (pq *PriorityQueue[T, V]) Dequeue() (value T, priority V, ok bool)
  • func (pq *PriorityQueue[T, V]) Enqueue(value T, priority V)
  • func (pq *PriorityQueue[T, V]) IsEmpty() bool
  • func (pq *PriorityQueue[T, V]) Items() []*Item[T, V]
  • func (pq *PriorityQueue[T, V]) Len() int
  • func (pq *PriorityQueue[T, V]) Less(i, j int) bool
  • func (pq *PriorityQueue[T, V]) Peek() (value T, priority V, ok bool)
  • func (pq *PriorityQueue[T, V]) Pop() any
  • func (pq *PriorityQueue[T, V]) Push(x any)
  • func (pq *PriorityQueue[T, V]) Remove(value T) bool
  • func (pq *PriorityQueue[T, V]) Set(value T, priority V) bool
  • func (pq *PriorityQueue[T, V]) String() string
  • func (pq *PriorityQueue[T, V]) Swap(i, j int)
  • func (pq *PriorityQueue[T, V]) ToSlice() []T
  • func (pq *PriorityQueue[T, V]) UnsafeItems() []*Item[T, V]
  • func (pq *PriorityQueue[T, V]) Values() []T

Variables

var (
	ErrInvalidItemType = errors.New("invalid item type")
)

Types

type HeapKind

type HeapKind int

const (
	// MinHeap yields items with the smallest priority first.
	MinHeap HeapKind = iota
	// MaxHeap yields items with the largest priority first.
	MaxHeap
)

type Item

type Item[T comparable, V any] struct {
	Value    T // Value identifies the item.
	Priority V // Priority determines the item's order in the queue.
	// contains filtered or unexported fields
}

Item represents an element in the priority queue with a value and priority.

type PriorityQueue

type PriorityQueue[T comparable, V cmp.Ordered] struct {
	// contains filtered or unexported fields
}

PriorityQueue is a generic priority queue implementation using a heap. It maintains items with associated priorities, supporting both min-heap and max-heap configurations. The queue uses a map for O(1) value lookups and supports custom comparators for priority ordering.

func New

func New[T comparable, V cmp.Ordered](kind HeapKind) *PriorityQueue[T, V]

New creates a new priority queue with the default comparator for ordered types. It initializes an empty queue with the specified heap kind (MinHeap or MaxHeap). The type V must implement cmp.Ordered (e.g., int, float64, string).

Args:

kind: The heap type (MinHeap or MaxHeap).

Returns:

A pointer to an initialized PriorityQueue.

Example:

pq := New[int, int](MinHeap)
pq.Put(1, 10)

func NewWith

func NewWith[T comparable, V cmp.Ordered](kind HeapKind, cmp cmp.Comparator[V]) *PriorityQueue[T, V]

NewWith creates a new priority queue with a custom comparator for priorities. It initializes an empty queue with the specified heap kind and comparator.

Args:

kind: The heap type (MinHeap or MaxHeap).
cmp: A comparator function for priorities.

Returns:

A pointer to an initialized PriorityQueue.

Example:

pq := NewWith[string, int](MaxHeap, cmp.Compare[int])
pq.Put("task1", 5)

func (*PriorityQueue[T, V]) Clear

func (pq *PriorityQueue[T, V]) Clear()

Clear removes all items from the queue and resets its internal state. Time complexity: O(1).

func (*PriorityQueue[T, V]) Dequeue

func (pq *PriorityQueue[T, V]) Dequeue() (value T, priority V, ok bool)

Dequeue removes and returns the item with the highest/lowest priority, based on the heap kind. Returns nil if the queue is empty. Time complexity: O(log n).

func (*PriorityQueue[T, V]) Enqueue

func (pq *PriorityQueue[T, V]) Enqueue(value T, priority V)

Enqueue adds a value with the specified priority to the queue. If the value already exists, it updates the priority.

Time complexity: O(log n).

func (*PriorityQueue[T, V]) IsEmpty

func (pq *PriorityQueue[T, V]) IsEmpty() bool

IsEmpty checks if the queue contains no items. Time complexity: O(1).

func (*PriorityQueue[T, V]) Items

func (pq *PriorityQueue[T, V]) Items() []*Item[T, V]

Items returns a copy of the heap slice containing all queue items. This is a safe operation that doesn't expose the internal heap structure. Time complexity: O(n).

func (*PriorityQueue[T, V]) Len

func (pq *PriorityQueue[T, V]) Len() int

Len returns the number of items in the queue. Time complexity: O(1).

func (*PriorityQueue[T, V]) Less

func (pq *PriorityQueue[T, V]) Less(i, j int) bool

Less determines the ordering of items based on their priorities and heap kind. Time complexity: O(1).

func (*PriorityQueue[T, V]) Peek

func (pq *PriorityQueue[T, V]) Peek() (value T, priority V, ok bool)

Peek returns the item with the highest/lowest priority, based on the heap kind. Returns nil if the queue is empty. Time complexity: O(1).

func (*PriorityQueue[T, V]) Pop

func (pq *PriorityQueue[T, V]) Pop() any

Pop removes and returns the top item from the heap. Time complexity: O(log n).

func (*PriorityQueue[T, V]) Push

func (pq *PriorityQueue[T, V]) Push(x any)

Push adds an item to the heap. Time complexity: O(log n).

func (*PriorityQueue[T, V]) Remove

func (pq *PriorityQueue[T, V]) Remove(value T) bool

Remove removes the item with the specified value from the queue. Returns true if the item was removed, false otherwise. Time complexity: O(log n).

func (*PriorityQueue[T, V]) Set

func (pq *PriorityQueue[T, V]) Set(value T, priority V) bool

Set changes the priority of an existing value in the queue.

Time complexity: O(log n).

func (*PriorityQueue[T, V]) String

func (pq *PriorityQueue[T, V]) String() string

String returns a string representation of the queue.

func (*PriorityQueue[T, V]) Swap

func (pq *PriorityQueue[T, V]) Swap(i, j int)

Swap exchanges two items in the heap and updates their indices. Time complexity: O(1).

func (*PriorityQueue[T, V]) ToSlice

func (pq *PriorityQueue[T, V]) ToSlice() []T

ToSlice returns a copy of the heap slice containing all queue items. This is a safe operation that doesn't expose the internal heap structure. Time complexity: O(n).

func (*PriorityQueue[T, V]) UnsafeItems

func (pq *PriorityQueue[T, V]) UnsafeItems() []*Item[T, V]

UnsafeItems returns a direct reference to the internal heap slice. WARNING: This is unsafe and should only be used for read-only operations. Modifying the returned slice directly may corrupt the heap structure. Time complexity: O(1).

func (*PriorityQueue[T, V]) Values

func (pq *PriorityQueue[T, V]) Values() []T

Values returns a copy of the values in the queue. This is a safe operation that doesn't expose the internal heap structure. Time complexity: O(n).