heap

Documentation

Overview

Package heap provides the implementation for heaps.

Index

• type Heap
  • func New(id string, vals []float64, cmp func(float64, float64) bool) *Heap
  • func (h *Heap) Len() int
  • func (h *Heap) Less(i, j int) bool
  • func (h *Heap) Peek() float64
  • func (h *Heap) Pop() interface{}
  • func (h *Heap) Push(x interface{})
  • func (h *Heap) Remove(item *Item)
  • func (h *Heap) Swap(i, j int)
  • func (h *Heap) Update(item *Item, val float64)
  • func (h *Heap) Values() []float64
• type Item

Types

type Heap

type Heap struct {
	ID string
	// contains filtered or unexported fields
}

Heap implements a heap data structure.

func New

func New(id string, vals []float64, cmp func(float64, float64) bool) *Heap

New initializes a new Heap.

func (*Heap) Len

func (h *Heap) Len() int

func (*Heap) Less

func (h *Heap) Less(i, j int) bool

func (*Heap) Peek

func (h *Heap) Peek() float64

Peek returns the element at the top of the heap, without popping it.

func (*Heap) Pop

func (h *Heap) Pop() interface{}

Pop removes element Len() - 1 from the heap. This satisfies heapops.Interface.

func (*Heap) Push

func (h *Heap) Push(x interface{})

Push adds an element to the heap. This satisfies heapops.Interface.

func (*Heap) Remove

func (h *Heap) Remove(item *Item)

Remove removes an item from the heap.

func (*Heap) Swap

func (h *Heap) Swap(i, j int)

func (*Heap) Update

func (h *Heap) Update(item *Item, val float64)

Update modifies the value of an item and fixes any violations of the heap invariant. This is equivalent to manually removing the item and pushing a new one in, but is less expensive.

func (*Heap) Values

func (h *Heap) Values() []float64

Values returns the values stored by the heap; this is mainly for debugging purposes.

type Item

type Item struct {
	Val float64
	// field that can be used for bookkeeping (i.e.
	// keeping track of the item as it gets moved
	// between multiple heaps; this is useful for
	// HeapMedian)
	HeapID string
	// contains filtered or unexported fields
}

Item represents an item in the heap; in particular, it contains not only the value, but also the index of the item within the heap. This is useful for the case where we want to replace an item in the heap and fix its structure; the container/heap.Fix method requires the index of the item that possibly violates the heap invariant.