queue

Documentation

Overview

Package queue provides a generic priority queue.

Index

• type Lesser
• type PriorityQueue
  • func NewPriorityQueue[T Lesser[T]]() *PriorityQueue[T]
  • func (p *PriorityQueue[T]) Len() int
  • func (p *PriorityQueue[T]) Pop() (*T, bool)
  • func (p *PriorityQueue[T]) Push(x T)

Types

type Lesser

type Lesser[T any] interface {
	LessThan(T) bool
}

Lesser is an interface to enable generic structs to be elements of a priority queue. Any struct can become a priority queue element by defining the LessThan method and initializing a new PriorityQueue.

	(s myStruct) LessThan(other myStruct) bool
 q := NewPriorityQueue[myStruct]()

type PriorityQueue

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

PriorityQueue implements a priority queue.

func NewPriorityQueue

func NewPriorityQueue[T Lesser[T]]() *PriorityQueue[T]

NewPriorityQueue returns an empty priority queue.

func (*PriorityQueue[T]) Len

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

Len returns the length of the queue.

func (*PriorityQueue[T]) Pop

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

Pop removes the top element of the queue and restructures it in log(n) time.

func (*PriorityQueue[T]) Push

func (p *PriorityQueue[T]) Push(x T)

Push adds a new element to the queue and puts it in the correct place.