tinykv

Documentation

Overview

Package heap provides heap operations for any type that implements heap.Interface. A heap is a tree with the property that each node is the minimum-valued node in its subtree.

The minimum element in the tree is the root, at index 0.

A heap is a common way to implement a priority queue. To build a priority queue, implement the Heap interface with the (negative) priority as the ordering for the Less method, so Push adds items while Pop removes the highest-priority item from the queue. The Examples include such an implementation; the file example_pq_test.go has the complete source.

Index

• func Fix(h Interface, i int)
• func Init(h Interface)
• func Push(h Interface, x Val)
• type Interface
• type KV
  • func New[T any](expirationInterval time.Duration, onExpire ...func(k string, v T)) KV[T]
• type Val
  • func Pop(h Interface) Val
  • func Remove(h Interface, i int) Val

Functions

func Fix

func Fix(h Interface, i int)

Fix re-establishes the heap ordering after the element at index i has changed its value. Changing the value of the element at index i and then calling Fix is equivalent to, but less expensive than, calling Remove(h, i) followed by a Push of the new value. The complexity is O(log(n)) where n = h.Len().

func Init

func Init(h Interface)

A heap must be initialized before any of the heap operations can be used. Init is idempotent with respect to the heap invariants and may be called whenever the heap invariants may have been invalidated. Its complexity is O(n) where n = h.Len().

func Push

func Push(h Interface, x Val)

Push pushes the element x onto the heap. The complexity is O(log(n)) where n = h.Len().

Types

type Interface

type Interface interface {
	Len() int
	Less(i, j int) bool
	Swap(i, j int)
	Push(x Val) // add x as element Len()
	Pop() Val   // remove and return element Len() - 1.
}

Any type that implements heap.Interface may be used as a min-heap with the following invariants (established after Init has been called or if the data is empty or sorted):

!h.Less(j, i) for 0 <= i < h.Len() and 2*i+1 <= j <= 2*i+2 and j < h.Len()

Note that Push and Pop in this interface are for package heap's implementation to call. To add and remove things from the heap, use heap.Push and heap.Pop.

type KV

type KV[T any] interface {
	Delete(k string)
	Get(k string) (v T, ok bool)
	Keys() (keys []string)
	Values() (values []T)
	Entries() (entries map[string]entry[T])
	Put(k string, v T, expiresAfter time.Duration) error
	Stop()
	MarshalJSON() ([]byte, error)
	UnmarshalJSON(b []byte) error
}

KV is a registry for values (like/is a concurrent map) with timeout and sliding timeout

func New

func New[T any](expirationInterval time.Duration, onExpire ...func(k string, v T)) KV[T]

New creates a new *store, onExpire is for notification (must be fast).

type Val

type Val = interface{}

func Pop

func Pop(h Interface) Val

Pop removes the minimum element (according to Less) from the heap and returns it. The complexity is O(log(n)) where n = h.Len(). It is equivalent to Remove(h, 0).

func Remove

func Remove(h Interface, i int) Val

Remove removes the element at index i from the heap. The complexity is O(log(n)) where n = h.Len().