heap

Documentation

Overview

Package heap provide a min-heap implementation called Heap.

Example (HeapSort)

package main

import (
	"fmt"

	"github.com/ServiceWeaver/weaver/internal/heap"
)

func main() {
	less := func(x, y int) bool { return x < y }
	ints := heap.New(less)
	unsorted := []int{2, 9, 6, 3, 8, 7, 4, 1, 5}
	sorted := []int{}

	for _, x := range unsorted {
		ints.Push(x)
	}
	for ints.Len() > 0 {
		x, _ := ints.Pop()
		sorted = append(sorted, x)
	}
	fmt.Println(sorted)
}

Output:

[1 2 3 4 5 6 7 8 9]

Index

• type Heap
  • func New[T any](less func(x, y T) bool) *Heap[T]
  • func (h *Heap[T]) Len() int
  • func (h *Heap[T]) Peek() (val T, ok bool)
  • func (h *Heap[T]) Pop() (val T, ok bool)
  • func (h *Heap[T]) Push(val T)

Examples

• Package (HeapSort)
• Heap.Peek
• Heap.Pop
• New

Types

type Heap

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

Heap is a generic min-heap. Modifying an element while it is on the heap invalidates the heap.

func New

func New[T any](less func(x, y T) bool) *Heap[T]

New returns a new empty heap, with elements sorted using the provided comparator function.

Example

package main

import (
	"github.com/ServiceWeaver/weaver/internal/heap"
)

func main() {
	// Create a heap of ints.
	heap.New(func(x, y int) bool { return x < y })

	// Create a heap of strings.
	heap.New(func(x, y string) bool { return x < y })
}

func (*Heap[T]) Len

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

Len returns the length of the heap.

func (*Heap[T]) Peek

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

Peek returns the least element from the heap, if the heap is non-empty. Unlike Pop, Peek does not modify the heap.

Example

package main

import (
	"fmt"

	"github.com/ServiceWeaver/weaver/internal/heap"
)

func main() {
	ints := heap.New(func(x, y int) bool { return x < y })
	fmt.Println(ints.Peek())
	ints.Push(42)
	fmt.Println(ints.Peek())
}

Output:

0 false
42 true

func (*Heap[T]) Pop

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

Pop pops the least element from the heap, if the heap is non-empty.

Example

package main

import (
	"fmt"

	"github.com/ServiceWeaver/weaver/internal/heap"
)

func main() {
	ints := heap.New(func(x, y int) bool { return x < y })
	ints.Push(2)
	ints.Push(1)
	fmt.Println(ints.Pop())
	fmt.Println(ints.Pop())
	fmt.Println(ints.Pop())
}

Output:

1 true
2 true
0 false

func (*Heap[T]) Push

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

Push pushes an element onto the heap.