loser

Documentation

Index

• type Tree
  • func New[E cmp.Ordered](lists [][]E, maxVal E) *Tree[E]
  • func (t *Tree[E]) Next() bool
  • func (t *Tree[E]) Push(list []E)
  • func (t *Tree[E]) Winner() E

Types

type Tree

type Tree[E cmp.Ordered] struct {
	// contains filtered or unexported fields
}

A loser tree is a binary tree laid out such that nodes N and N+1 have parent N/2. We store M leaf nodes in positions M...2M-1, and M-1 internal nodes in positions 1..M-1. Node 0 is a special node, containing the winner of the contest.

func New

func New[E cmp.Ordered](lists [][]E, maxVal E) *Tree[E]

func (*Tree[E]) Next

func (t *Tree[E]) Next() bool

func (*Tree[E]) Push

func (t *Tree[E]) Push(list []E)

Add a new list to the merge set

func (*Tree[E]) Winner

func (t *Tree[E]) Winner() E