binaryheap

README

Binary Heap

A binary heap is a heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues. The binary heap was introduced by J. W. J. Williams in 1964, as a data structure for heapsort.

A binary heap is defined as a binary tree with two additional constraints:

• Shape property: a binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
• Heap property: the key stored in each node is either greater than or equal to (≥) or less than or equal to (≤) the keys in the node's children, according to some total order.

Heaps where the parent key is greater than or equal to (≥) the child keys are called max-heaps; those where it is less than or equal to (≤) are called min-heaps. Efficient (logarithmic time) algorithms are known for the two operations needed to implement a priority queue on a binary heap: inserting an element, and removing the smallest or largest element from a min-heap or max-heap, respectively. Binary heaps are also commonly employed in the heapsort sorting algorithm, which is an in-place algorithm because binary heaps can be implemented as an implicit data structure, storing keys in an array and using their relative positions within that array to represent child-parent relationships.

Wikipedia

Documentation

Index

• Constants
• Variables
• type BinaryHeap
  • func New(elements map[int]interface{}, heapType heapType) (*BinaryHeap, error)
  • func (s *BinaryHeap) Insert(priority int, value interface{}) error
  • func (h *BinaryHeap) Peek() (interface{}, error)
  • func (h *BinaryHeap) Remove(priority int) error
  • func (h *BinaryHeap) Top() (interface{}, error)
  • func (h *BinaryHeap) Update(priority int, newPriority int) error

Constants

const (
	Min heapType = 1
	Max heapType = 2
)

Variables

var ErrBinaryHeapIsEmpty = fmt.Errorf("binary heap is empty")

var ErrNotFound = fmt.Errorf("value with priority not found")

Types

type BinaryHeap

type BinaryHeap struct {
	// contains filtered or unexported fields
}

func New

func New(elements map[int]interface{}, heapType heapType) (*BinaryHeap, error)

@TODO: need to add support for multiple same-priority node insertion

func (*BinaryHeap) Insert

func (s *BinaryHeap) Insert(priority int, value interface{}) error

func (*BinaryHeap) Peek

func (h *BinaryHeap) Peek() (interface{}, error)

func (*BinaryHeap) Remove

func (h *BinaryHeap) Remove(priority int) error

func (*BinaryHeap) Top

func (h *BinaryHeap) Top() (interface{}, error)

func (*BinaryHeap) Update

func (h *BinaryHeap) Update(priority int, newPriority int) error