binary_heap

Documentation

Index

• type BinaryHeap
  • func Heapify[T any](slice []T, cmp func(T, T) int) BinaryHeap[T]
  • func New[T any](predicate func(T, T) int) BinaryHeap[T]
  • func (d *BinaryHeap[T]) Begin() Iterator[T]
  • func (d *BinaryHeap[T]) Cap() int
  • func (d *BinaryHeap[T]) Len() int
  • func (b *BinaryHeap[T]) Pop()
  • func (b *BinaryHeap[T]) Push(e T)
  • func (b *BinaryHeap[T]) Top() T
• type Iterator
  • func (i *Iterator[T]) Get() T
  • func (i *Iterator[T]) HasNext() bool
  • func (i *Iterator[T]) Next()

Examples

• BinaryHeap.Begin
• BinaryHeap.Cap
• BinaryHeap.Len
• BinaryHeap.Pop
• BinaryHeap.Push
• BinaryHeap.Top
• Heapify
• Iterator
• New

Types

type BinaryHeap

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

A max binary heap.

interface: PriorityQueue

func Heapify

func Heapify[T any](slice []T, cmp func(T, T) int) BinaryHeap[T]

Heapify the slice using cmp as predicate.

Example

// Create a max heap from a slice
slice := []int{4, 2, 7, 1, 9, 5}
maxHeap := Heapify(slice, func(i, j int) int { return i - j })
fmt.Println(maxHeap.slice)

Output:

[9 4 7 1 2 5]

func New

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

Example

// Create a max heap
slice := []int{4, 2, 7, 1, 9, 5}
maxHeap := New(func(i, j int) int { return i - j })
for _, n := range slice {
	maxHeap.Push(n)
}
fmt.Println(maxHeap.slice)

Output:

[9 7 5 1 2 4]

func (*BinaryHeap[T]) Begin

func (d *BinaryHeap[T]) Begin() Iterator[T]

Return an iterator points to the top.

Example

// Get the top element of the heap
slice := []int{4, 2, 7, 1, 9, 5}
maxHeap := Heapify(slice, func(i, j int) int { return i - j })
topElement := maxHeap.Begin()
fmt.Println(topElement.Get())

Output:

9

func (*BinaryHeap[T]) Cap

func (d *BinaryHeap[T]) Cap() int

Return the capacity.

Example

// Get the capacity of the heap
slice := []int{4, 2, 7, 1, 9, 5}
maxHeap := Heapify(slice, func(i, j int) int { return i - j })
capacity := maxHeap.Cap()
fmt.Println(capacity)

Output:

6

func (*BinaryHeap[T]) Len

func (d *BinaryHeap[T]) Len() int

Return the number of element.

Example

// Get the length of the heap
slice := []int{4, 2, 7, 1, 9, 5}
maxHeap := Heapify(slice, func(i, j int) int { return i - j })
length := maxHeap.Len()
fmt.Println(length)

Output:

6

func (*BinaryHeap[T]) Pop

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

Remove the top element from the heap.

Example

// Pop the top element from the heap
slice := []int{4, 2, 7, 1, 9, 5}
maxHeap := Heapify(slice, func(i, j int) int { return i - j })
maxHeap.Pop()
fmt.Println(maxHeap.slice)

Output:

[7 4 5 1 2]

func (*BinaryHeap[T]) Push

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

Add e to the heap.

Example

// Push an element into the heap
slice := []int{4, 2, 7, 1, 9, 5}
maxHeap := Heapify(slice, func(i, j int) int { return i - j })
maxHeap.Push(8)
fmt.Println(maxHeap.slice)

Output:

[9 4 8 1 2 5 7]

func (*BinaryHeap[T]) Top

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

Return the top of the heap.

Example

// Get the top element of the heap
slice := []int{4, 2, 7, 1, 9, 5}
maxHeap := Heapify(slice, func(i, j int) int { return i - j })
topElement := maxHeap.Top()
fmt.Println(topElement)

Output:

9

type Iterator

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

A binary heap iterator that traverse from max to min elements.

Example

// Iterate through the heap
slice := []int{4, 2, 7, 1, 9, 5}
maxHeap := Heapify(slice, func(i, j int) int { return i - j })
for iter := maxHeap.Begin(); iter.HasNext(); iter.Next() {
	fmt.Println(iter.Get())
}

Output:

9
7
5
4
2
1

func (*Iterator[T]) Get

func (i *Iterator[T]) Get() T

Return the value.

func (*Iterator[T]) HasNext

func (i *Iterator[T]) HasNext() bool

Return true if can advance.

func (*Iterator[T]) Next

func (i *Iterator[T]) Next()

Advance the iterator.