heap

README

heap

A collection of basic abstract heap data structures.

Implicit Heap description example

Dynamic Min & Max Implicit heaps.

An implicit heap is an implementation of a heap consisting of a complete binary tree whose nodes contain the heap items, one node per item.

Insert example:

Implicit Heap Implementation

Insert (push) and remove min/max (pop) have O(log n) complexity. The size of the slices (array) is dynamic, with a minimum of 8 elements and doubles each time is full, and shrink to half each time it's N < size/4.

The keys are intand values can be any type interface{}.

For best performance use a small non sparsed Key value distribution. (100-300 incremental values).

Documentation

Overview

Package heap contains fast implementations, concurrent safe for basic tree data structures.

Implicit Heap - O(log n) Min&Max heap/priority queue, used to store key/value pairs with fast access to the minimum/maximum element.

Index

• type ImplicitHeap
• type ImplicitHeapMax
  • func NewImplicitHeapMax(autoLockMutex bool) *ImplicitHeapMax
• type ImplicitHeapMin
  • func NewImplicitHeapMin(autoLockMutex bool) *ImplicitHeapMin
  • func (h *ImplicitHeapMin) HasElement() bool
  • func (h *ImplicitHeapMin) IsDepleted() bool
  • func (h *ImplicitHeapMin) Len() int
  • func (h *ImplicitHeapMin) Peek() (v interface{}, ok bool)
  • func (h *ImplicitHeapMin) Pop() (v interface{}, ok bool)
  • func (h *ImplicitHeapMin) Push(priority int, value interface{})
  • func (h *ImplicitHeapMin) Reset()

Examples

• ImplicitHeapMax
• ImplicitHeapMin

Types

type ImplicitHeap

type ImplicitHeap interface {
	Push(priority int, v interface{})
	Pop() (v interface{}, ok bool)
	Peek() (v interface{}, ok bool)
	Reset()
	Lock()
	Unlock()
	IsDepleted() bool
	HasElement() bool
	Len() int
}

ImplicitHeap is an interface for dynamic min & max implicit heaps.

An implicit heap is an implementation of a heap consisting of a complete binary tree whose nodes contain the heap items, one node per item.

It can be used as a Priority queue as well. It can store a series of objects (of any type) associated with a key (priority). Use ImplicitHeapMin to always get the smallest key (priority) and ImplicitHeapMax for the largest key.

For best performance use a small non sparsed Key value distribution. (100-300 incremental values).

type ImplicitHeapMax

type ImplicitHeapMax struct {
	ImplicitHeapMin
}

ImplicitHeapMax A dynamic list of numbers, stored as a Binary tree in a dynamic slice. Used to quickly get the biggest number from a list/queue/priority queue.

Inherits all the methods of ImplicitHeapMin.

Example

autoLockMutex := false
maxPriority := NewImplicitHeapMax(autoLockMutex)
//add 3 priorities, with any data types
maxPriority.Push(3, false)
maxPriority.Push(1, "alfa")
maxPriority.Push(9, []int{0, 0})

max, _ := maxPriority.Pop()
fmt.Printf("max is %v", max)

Output:

max is [0 0]

func NewImplicitHeapMax

func NewImplicitHeapMax(autoLockMutex bool) *ImplicitHeapMax

NewImplicitHeapMax Builds an empty Implicit Heap Max struct.

type ImplicitHeapMin

type ImplicitHeapMin struct {
	sync.Mutex
	// contains filtered or unexported fields
}

ImplicitHeapMin A dynamic tree (list) of numbers, stored as a Binary tree in a dynamic slice. Used to quickly get the smallest number from a list/queue/priority queue.

It is a base struct for ImplicitHeapMax.

Example

autoLockMutex := false
minPriority := NewImplicitHeapMin(autoLockMutex)
//add 3 priorities, with any data types
minPriority.Push(3, false)
minPriority.Push(1, "alfa")
minPriority.Push(9, []int{0, 0})

min, _ := minPriority.Pop()
fmt.Printf("min is %v", min)

Output:

min is alfa

func NewImplicitHeapMin

func NewImplicitHeapMin(autoLockMutex bool) *ImplicitHeapMin

NewImplicitHeapMin Builds an empty ImplicitHeapMin

func (*ImplicitHeapMin) HasElement

func (h *ImplicitHeapMin) HasElement() bool

HasElement Check if the list has at least 1 elment left

func (*ImplicitHeapMin) IsDepleted

func (h *ImplicitHeapMin) IsDepleted() bool

IsDepleted Check if the list is empty

func (*ImplicitHeapMin) Len

func (h *ImplicitHeapMin) Len() int

Len How many elements are in the heap

func (*ImplicitHeapMin) Peek

func (h *ImplicitHeapMin) Peek() (v interface{}, ok bool)

Peek Find-* returns the first value (root element) O(1). For ImplicitHeapMin returns the value for the smallest key(priority). For ImplicitHeapMax returns the value for the largest key(priority). Does not mutate the list

func (*ImplicitHeapMin) Pop

func (h *ImplicitHeapMin) Pop() (v interface{}, ok bool)

Pop Delete-*, return the first value (root element) O(log(n)) For ImplicitHeapMin returns the value for the smallest key(priority). For ImplicitHeapMax returns the value for the largest key(priority). Removes the element from the list

func (*ImplicitHeapMin) Push

func (h *ImplicitHeapMin) Push(priority int, value interface{})

Push Insert a new key/value pair in the list.

func (*ImplicitHeapMin) Reset

func (h *ImplicitHeapMin) Reset()

Reset Feed all your data to the Garbage Collector.