treap

Documentation

Overview

Package treap implements a treap. See https://en.wikipedia.org/wiki/Treap for more details.

Index

• type Treap
  • func New[T constraints.Ordered]() *Treap[T]
  • func NewWithComparator[T any](comp func(T, T) int) *Treap[T]
  • func (t *Treap[T]) All() []T
  • func (t *Treap[T]) Contains(value T) bool
  • func (t *Treap[T]) Insert(value T)
  • func (t *Treap[T]) Remove(value T) bool
  • func (t *Treap[T]) SetSource(s rand.Source)
  • func (t *Treap[T]) Size() int

Types

type Treap

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

Treap represents a treap. Zero value of Treap is invalid treap, should be used only with New() or NewWithSource().

func New

func New[T constraints.Ordered]() *Treap[T]

New returns an initialized treap. rand.Rand is used with time.Now().UnixNano(). For custom rand.Rand use Treap.SetSource.

func NewWithComparator

func NewWithComparator[T any](comp func(T, T) int) *Treap[T]

NewWithComparator returns an initialized treap using given comparator.

func (*Treap[T]) All

func (t *Treap[T]) All() []T

All returns all elements from tree. Returned slice is sorted.

func (*Treap[T]) Contains

func (t *Treap[T]) Contains(value T) bool

Contains returns true if tree contains given value, false otherwise.

func (*Treap[T]) Insert

func (t *Treap[T]) Insert(value T)

Insert inserts value in a tree.

func (*Treap[T]) Remove

func (t *Treap[T]) Remove(value T) bool

Remove removes value from tree. Returns true if tree contained given value, false otherwise.

func (*Treap[T]) SetSource

func (t *Treap[T]) SetSource(s rand.Source)

SetSource sets rand source.

func (*Treap[T]) Size

func (t *Treap[T]) Size() int

Size returns size of the tree.