README
¶
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
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
Documentation
¶
Overview ¶
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 ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type Heap ¶
type Heap[T any] struct { // contains filtered or unexported fields }
Heap implements a binary heap.
func From ¶
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 ¶
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 (*Heap[T]) Peek ¶
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 ¶
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
Source Files