pqueue

Documentation

Index

• type Binomial
  • func NewBinomial[O cmp.Ordered]() *Binomial[O]
  • func (b *Binomial[O]) Merge(b2 *Binomial[O])
  • func (b *Binomial[O]) Pop() O
  • func (b *Binomial[O]) Push(p O)
  • func (b *Binomial[O]) Size() int
  • func (b *Binomial[O]) Top() O
• type Elem
• type Fixable
  • func NewFixable[P cmp.Ordered, V comparable](cap uint) *Fixable[P, V]
  • func (h *Fixable[P, V]) Del(v V)
  • func (h *Fixable[P, V]) Fix(p P, v V)
• type Heap
  • func NewHeap[P cmp.Ordered](cap uint) *Heap[P]
  • func (h *Heap[P]) Pop() P
  • func (h *Heap[P]) Push(v P)
  • func (h *Heap[P]) Top() P
• type Leftist
  • func NewLeftist[O cmp.Ordered]() *Leftist[O]
  • func (lh *Leftist[O]) Merge(other *Leftist[O])
  • func (lh *Leftist[O]) Peek() O
  • func (lh *Leftist[O]) Pop() O
  • func (lh *Leftist[O]) Push(o O)
  • func (lh *Leftist[O]) Size() int
  • func (lh *Leftist[O]) Top() O
• type Paired
  • func NewPaired[P cmp.Ordered, V any](cap uint) *Paired[P, V]
  • func (h *Paired[P, V]) Cap() int
  • func (h *Paired[P, V]) FixTop(p P)
  • func (h *Paired[P, V]) Pop() V
  • func (h *Paired[P, V]) PopPair() (P, V)
  • func (h *Paired[P, V]) PushPair(p P, v V)
  • func (h *Paired[P, V]) Size() int
  • func (h *Paired[P, V]) Top() V
  • func (h *Paired[P, V]) TopPair() (P, V)
• type PriorQueue

Examples

• Binomial
• Fixable
• Leftist

Types

type Binomial

type Binomial[O cmp.Ordered] struct {
	// contains filtered or unexported fields
}

Binomial is a binomial queue

Example

b := NewBinomial[int]()
b.Push(1)
b.Push(9)
b.Push(9)
b.Push(7)
b2 := NewBinomial[int]()
b2.Push(13)
b2.Push(11)
b.Merge(b2)
for b.Size() > 0 {
	fmt.Print(b.Pop(), ",")
}

Output:

1,7,9,9,11,13,

func NewBinomial

func NewBinomial[O cmp.Ordered]() *Binomial[O]

NewBinomial return a binomial queue with default capacity

func (*Binomial[O]) Merge

func (b *Binomial[O]) Merge(b2 *Binomial[O])

Merge bq1 to bq. ErrExceedCap returned when merge would exceed capacity

func (*Binomial[O]) Pop

func (b *Binomial[O]) Pop() O

func (*Binomial[O]) Push

func (b *Binomial[O]) Push(p O)

func (*Binomial[O]) Size

func (b *Binomial[O]) Size() int

Size get the current size of this binomial queue

func (*Binomial[O]) Top

func (b *Binomial[O]) Top() O

type Elem

type Elem[P cmp.Ordered, V any] struct {
	// contains filtered or unexported fields
}

type Fixable

type Fixable[P cmp.Ordered, V comparable] struct {
	Paired[P, V]
}

Example

pq := NewFixable[int, string](3)
pq.PushPair(1, "1")
pq.PushPair(9, "9")
pq.PushPair(9, "9")
pq.PushPair(7, "7")
for pq.Size() > 0 {
	fmt.Print(pq.Pop())
}
fmt.Println()

pq.PushPair(100, "1")
pq.PushPair(9, "9")
pq.PushPair(9, "9")
pq.PushPair(7, "7")
pq.PushPair(0, "x")
pq.Del("x")
pq.Fix(1, "1")
for pq.Size() > 0 {
	fmt.Print(pq.Pop())
}

Output:

1799
1799

func NewFixable

func NewFixable[P cmp.Ordered, V comparable](cap uint) *Fixable[P, V]

func (*Fixable[P, V]) Del

func (h *Fixable[P, V]) Del(v V)

func (*Fixable[P, V]) Fix

func (h *Fixable[P, V]) Fix(p P, v V)

Fix priority

type Heap

type Heap[P cmp.Ordered] struct {
	Paired[P, struct{}]
}

func NewHeap

func NewHeap[P cmp.Ordered](cap uint) *Heap[P]

func (*Heap[P]) Pop

func (h *Heap[P]) Pop() P

func (*Heap[P]) Push

func (h *Heap[P]) Push(v P)

func (*Heap[P]) Top

func (h *Heap[P]) Top() P

type Leftist

type Leftist[O cmp.Ordered] struct {
	// contains filtered or unexported fields
}

Example

b := NewLeftist[int]()
b.Push(1)
b.Push(9)
b.Push(9)
b.Push(7)
b2 := NewLeftist[int]()
b2.Push(13)
b2.Push(11)
b.Merge(b2)
for b.Size() > 0 {
	fmt.Print(b.Pop(), ",")
}

Output:

1,7,9,9,11,13,

func NewLeftist

func NewLeftist[O cmp.Ordered]() *Leftist[O]

func (*Leftist[O]) Merge

func (lh *Leftist[O]) Merge(other *Leftist[O])

func (*Leftist[O]) Peek

func (lh *Leftist[O]) Peek() O

func (*Leftist[O]) Pop

func (lh *Leftist[O]) Pop() O

func (*Leftist[O]) Push

func (lh *Leftist[O]) Push(o O)

func (*Leftist[O]) Size

func (lh *Leftist[O]) Size() int

func (*Leftist[O]) Top

func (lh *Leftist[O]) Top() O

type Paired

type Paired[P cmp.Ordered, V any] struct {
	// contains filtered or unexported fields
}

func NewPaired

func NewPaired[P cmp.Ordered, V any](cap uint) *Paired[P, V]

NewPaired make an empty heap. Specify a proper cap to reduce times of re-allocate elems slice

func (*Paired[P, V]) Cap

func (h *Paired[P, V]) Cap() int

func (*Paired[P, V]) FixTop

func (h *Paired[P, V]) FixTop(p P)

func (*Paired[P, V]) Pop

func (h *Paired[P, V]) Pop() V

func (*Paired[P, V]) PopPair

func (h *Paired[P, V]) PopPair() (P, V)

func (*Paired[P, V]) PushPair

func (h *Paired[P, V]) PushPair(p P, v V)

func (*Paired[P, V]) Size

func (h *Paired[P, V]) Size() int

func (*Paired[P, V]) Top

func (h *Paired[P, V]) Top() V

func (*Paired[P, V]) TopPair

func (h *Paired[P, V]) TopPair() (P, V)

type PriorQueue

type PriorQueue[P cmp.Ordered] interface {
	Push(P)
	Pop() P
	Top() P
	Size() int
}