binomial_heap

Documentation

Index

• type BinomialHeap
  • func New[T any](predicate func(T, T) int) BinomialHeap[T]
  • func (b *BinomialHeap[T]) Len() int
  • func (b *BinomialHeap[T]) Merge(heap BinomialHeap[T])
  • func (b *BinomialHeap[T]) Pop()
  • func (b *BinomialHeap[T]) Push(e T)
  • func (b *BinomialHeap[T]) Top() T

Examples

• BinomialHeap.Len
• BinomialHeap.Merge
• BinomialHeap.Pop
• BinomialHeap.Push
• BinomialHeap.Top

Types

type BinomialHeap

type BinomialHeap[T any] struct {
	// contains filtered or unexported fields
}

A max binomial heap.

It has higher constant for insert and pop, but supports merging in O(log(len)).

interface: PriorityQueue

func New

func New[T any](predicate func(T, T) int) BinomialHeap[T]

func (*BinomialHeap[T]) Len

func (b *BinomialHeap[T]) Len() int

Return the number of element.

Example

heap := New(func(a, b int) int { return a - b })
fmt.Println(heap.Len())
heap.Push(123)
fmt.Println(heap.Len())

Output:

0
1

func (*BinomialHeap[T]) Merge

func (b *BinomialHeap[T]) Merge(heap BinomialHeap[T])

Merge and destruct the heap into the current heap.

Example

// Merge two binomial heaps and print the top element after merging
heap1 := New(func(a, b int) int { return a - b })
heap1.Push(5)
heap1.Push(3)

heap2 := New(func(a, b int) int { return a - b })
heap2.Push(10)
heap2.Push(8)

heap1.Merge(heap2)
fmt.Println(heap1.Len())
fmt.Println(heap1.Top())

Output:

4
10

func (*BinomialHeap[T]) Pop

func (b *BinomialHeap[T]) Pop()

Remove the top element from the heap.

Example

heap := New(func(a, b int) int { return a - b })
heap.Push(5)
heap.Push(3)
heap.Push(7)
fmt.Println(heap.Top())
heap.Pop()
fmt.Println(heap.Top())

Output:

7
5

func (*BinomialHeap[T]) Push

func (b *BinomialHeap[T]) Push(e T)

Push e to the heap.

Example

heap := New(func(a, b int) int { return a - b })
heap.Push(5)
heap.Push(3)
heap.Push(7)
fmt.Println(heap.Len())
heap.Push(10)
fmt.Println(heap.Len())
fmt.Println(heap.Top())

Output:

3
4
10

func (*BinomialHeap[T]) Top

func (b *BinomialHeap[T]) Top() T

Return the top of the heap.

Example

heap := New(func(a, b int) int { return a - b })
heap.Push(5)
heap.Push(3)
heap.Push(7)
fmt.Println(heap.Top())

Output:

7