peap

README

Intrusive peap in Go

An implementation of a pointer-based (array-less) intrusive min-heap. Peap is a portmanteau of pointer heap.

An intrusive data structure requires elements to embed a part of the data structure. This improves performance by reducing allocations.

This peap is mostly for novelty purposes as it preforms worse than container/heap for all but very small heaps, even in the best possible case. An array-based heap will be faster due to the cost of pointer chasing. Even with container/heap doing interface conversions and array doubling, it amortizes to being faster at somewhere fewer than 10 elements in the heap. Although it does release memory when no longer needed, adding array shrinking to container/heap in a wrapper would be simpler and likely preform better.

Documentation

Overview

Package peap provides the implementation of a pointer-based (array-less) intrusive min-heap. Peap is a portmanteau of pointer heap.

Recommended usage: Attach a little bo.

This package is based on the paper,"Peaps: Heaps implemented without arrays": https://www.cpp.edu/~ftang/courses/CS241/notes/Building_Heaps_With_Pointers.pdf

Index

• type Element
• type Entry
  • func (e *Entry[T]) Left() T
  • func (e *Entry[T]) Right() T
  • func (e *Entry[T]) SetLeft(elem T)
  • func (e *Entry[T]) SetRight(elem T)
• type Heap
  • func (h *Heap[T]) Len() int
  • func (h *Heap[T]) Peek() T
  • func (h *Heap[T]) Pop() T
  • func (h *Heap[T]) Push(e T)
  • func (h *Heap[T]) String() string
• type Linker

Types

type Element

type Element[T any] interface {
	comparable
	Linker[T]
	Less(T) bool
}

Element the item that is used at the API level.

N.B. Like Linker, this is unlikely to be an interface in most cases. If Element is not an interface, it must be a pointer.

type Entry

type Entry[T Element[T]] struct {
	// contains filtered or unexported fields
}

Entry is a default implementation of Linker. Users can embed this type in their structs to make them automatically implement most of the methods needed by Heap.

func (*Entry[T]) Left

func (e *Entry[T]) Left() T

Left returns left child of e.

func (*Entry[T]) Right

func (e *Entry[T]) Right() T

Right returns right child of e.

func (*Entry[T]) SetLeft

func (e *Entry[T]) SetLeft(elem T)

SetLeft assigns elem as the left child of e.

func (*Entry[T]) SetRight

func (e *Entry[T]) SetRight(elem T)

SetRight assigns elem as the right child of e.

type Heap

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

Heap implement a pointer-based min-heap.

func (*Heap[T]) Len

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

Len returns the number of Elements currently in the Heap.

func (*Heap[T]) Peek

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

Peek returns the next Element to be removed from the Heap.

func (*Heap[T]) Pop

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

Pop removes an Element from the Heap.

func (*Heap[T]) Push

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

Push adds an Element to the Heap.

func (*Heap[T]) String

func (h *Heap[T]) String() string

String implements fmt.Stringer.String.

type Linker

type Linker[T any] interface {
	Left() T
	Right() T
	SetLeft(T)
	SetRight(T)
}

Linker is the interface that objects must implement if they want to be added to and/or removed from Heap objects.

N.B. When substituted in a template instantiation, Linker doesn't need to be an interface, and in most cases won't be.