pqueue

Documentation

Overview

Package pqueue provides OOP-style priority queues.

For better performance, all functions in this package are unsafe for concurrency unless otherwise specified.

Index

• type PriorityQueue
  • func New[Item any](lessFn compare.LessFunc[Item], data container.Container[Item]) PriorityQueue[Item]

Types

type PriorityQueue

type PriorityQueue[Item any] interface {
	container.Container[Item]

	// Cap returns the current capacity of the queue.
	Cap() int

	// Enqueue adds items x into the queue.
	//
	// Time complexity: O(m log(m + n)), where m = len(x), n = pq.Len().
	Enqueue(x ...Item)

	// Dequeue removes and returns the highest-priority item in the queue.
	//
	// It panics if the queue is nil or empty.
	//
	// Time complexity: O(log n), where n = pq.Len().
	Dequeue() Item

	// Top returns the highest-priority item in the queue,
	// without modifying the queue.
	//
	// It panics if the queue is nil or empty.
	//
	// Time complexity: O(1).
	Top() Item

	// ReplaceTop replaces the highest-priority item with newX and
	// returns the current highest-priority item.
	//
	// It panics if the queue is nil or empty.
	//
	// Time complexity: O(log n), where n = pq.Len().
	ReplaceTop(newX Item) Item

	// Clear removes all items in the queue and asks to release the memory.
	Clear()
}

PriorityQueue is an interface representing a priority queue.

Its method Range may not access items in a priority-related order. It only guarantees that each item is accessed once.

func New

func New[Item any](
	lessFn compare.LessFunc[Item],
	data container.Container[Item],
) PriorityQueue[Item]

New creates a new priority queue. In this priority queue, the smaller the item (compared by the function lessFn), the higher its priority.

lessFn is a function to report whether a < b. It must describe a strict weak ordering. See <https://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings> for details.

Note that floating-point comparison (the < operator on float32 or float64 values) is not a strict weak ordering when not-a-number (NaN) values are involved.

data is the initial items added to the queue.

It panics if lessFn is nil.