heap

README

heap

A generic heap implementation for Go.

It's advanage over Go's container/heap package is less code is required be written to use it. While this code is not overly complex, it is not out-of-the-box and certainly more error prone. See the IntHeap and Priority Queue samples from official documentation to get a feel for overhead code required by the standard library implementation.

It rivals the performance of container/heap. After several trivial benchmarks, it constantly runs slower for Push operations and consistently faster for Pop operatations. If performance is an important requirement, it's worth building out the benchmark tests more.

Sample Benchmark Output from an M1 MacBook Air:

go test -bench .
goos: darwin
goarch: arm64
pkg: github.com/danielwchapman/heap
BenchmarkIntPush-8                      42510336                27.25 ns/op
BenchmarkContainerIntPush-8             100000000               18.59 ns/op
BenchmarkIntPop-8                        8255620               198.7 ns/op
BenchmarkContainerIntPop-8               6659751               233.2 ns/op
BenchmarkStructPush-8                   14317743                87.51 ns/op
BenchmarkContainerStructPush-8          12182853               106.0 ns/op
BenchmarkStructPop-8                     3216393               508.5 ns/op
BenchmarkContainerStructPop-8            2928676               587.8 ns/op
PASS
ok      github.com/danielwchapman/heap  15.639s

Benchmark tests with container in the name refer to benchmarking the container/heap package for comparision.

Installation

go get github.com/danielwchapman/heap           

Testing

go test ./...

go test -bench .

Documentation

Overview

Package heap is a generic heap implementation.

Index

• type Heap
  • func From[T any](less func(a, b T) bool, elements ...T) (Heap[T], error)
  • func Make[T any](less func(a, b T) bool, cap int) Heap[T]
  • func (h *Heap[T]) Cap() int
  • func (h *Heap[T]) Len() int
  • func (h *Heap[T]) Peek() (T, bool)
  • func (h *Heap[T]) Pop() (T, bool)
  • func (h *Heap[T]) Push(t T)

Types

type Heap

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

func From

func From[T any](less func(a, b T) bool, elements ...T) (Heap[T], error)

func Make

func Make[T any](less func(a, b T) bool, cap int) Heap[T]

MakeHeap makes a heap. For a max heap, functional parameter 'less' must return true when item a < b and false otherwise. For a min heap, 'less' must return true when item a > b and false otherwise. 'cap' is the capcity guess of the maximum size of the heap and follows the same rules a capacity for a slice.

func (*Heap[T]) Cap

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

Cap returns the underlying capacity of the heap. This can grow.

func (*Heap[T]) Len

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

Len returns the number of items in the heap.

func (*Heap[T]) Peek

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

Peek returns the top of the heap and true if there are items in the heap. It returns false when there are no items in the heap. Its runs in constant time.

func (*Heap[T]) Pop

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

Pop returns the top item of the heap and removes this item from the heap. It returns true when there is at least 1 item in the heap and false otherwise. It runs in O(log n) where n is the size of the heap.

func (*Heap[T]) Push

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

Push adds a new item into the heap. It runs in time O(log n) where n is the size of the heap.