heap

heap

import "github.com/zyedidia/generic/heap"

Package heap provides an implementation of a binary heap. A binary heap (binary min-heap) is a tree with the property that each node is the minimum-valued node in its subtree.

Example

package main

import (
	"fmt"

	"github.com/zyedidia/generic/heap"
)

func main() {
	heap := heap.New(func(a, b int) bool { return a < b })

	heap.Push(5)
	heap.Push(2)
	heap.Push(3)

	v, _ := heap.Pop()
	fmt.Println(v)

	v, _ = heap.Peek()
	fmt.Println(v)
}

Output

2
3

Index

• type Heap
  • func From[T any](less g.LessFn[T], t ...T) *Heap[T]
  • func FromSlice[T any](less g.LessFn[T], data []T) *Heap[T]
  • func New[T any](less g.LessFn[T]) *Heap[T]
  • func (h *Heap[T]) Peek() (T, bool)
  • func (h *Heap[T]) Pop() (T, bool)
  • func (h *Heap[T]) Push(x T)
  • func (h *Heap[T]) Size() int

type Heap

Heap implements a binary heap.

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

func From

func From[T any](less g.LessFn[T], t ...T) *Heap[T]

From returns a new heap with the given less function and initial data.

Example

package main

import (
	"fmt"

	"github.com/zyedidia/generic/heap"
)

func main() {
	heap := heap.From(func(a, b int) bool { return a < b }, 5, 2, 3)

	v, _ := heap.Pop()
	fmt.Println(v)

	v, _ = heap.Peek()
	fmt.Println(v)
}

Output

2
3

func FromSlice

func FromSlice[T any](less g.LessFn[T], data []T) *Heap[T]

FromSlice returns a new heap with the given less function and initial data. The `data` is not copied and used as the inside array.

Example

package main

import (
	"fmt"

	"github.com/zyedidia/generic/heap"
)

func main() {
	heap := heap.FromSlice(func(a, b int) bool { return a > b }, []int{-1, 5, 2, 3})

	v, _ := heap.Pop()
	fmt.Println(v)

	v, _ = heap.Peek()
	fmt.Println(v)
}

Output

5
3

func New

func New[T any](less g.LessFn[T]) *Heap[T]

New returns a new heap with the given less function.

func (*Heap[T]) Peek

func (h *Heap[T]) Peek() (T, bool)

Peek returns the minimum element from the heap without removing it. if the heap is empty, it returns zero value and false.

func (*Heap[T]) Pop

func (h *Heap[T]) Pop() (T, bool)

Pop removes and returns the minimum element from the heap. If the heap is empty, it returns zero value and false.

Example

package main

import (
	"fmt"

	"github.com/zyedidia/generic/heap"
)

func main() {
	heap := heap.New(func(a, b int) bool { return a < b })

	heap.Push(5)

	v, ok := heap.Pop()
	fmt.Println(v, ok)

	// pop on empty
	v, ok = heap.Pop()
	fmt.Println(v, ok)
}

Output

5 true
0 false

func (*Heap[T]) Push

func (h *Heap[T]) Push(x T)

Push pushes the given element onto the heap.

func (*Heap[T]) Size

func (h *Heap[T]) Size() int

Size returns the number of elements in the heap.

Generated by gomarkdoc