I am writing a collection of packages for different data structures in GO.
Why? To learn Go, practice basic structures and learning to code fast concurrent algorithms.
All the packages have 100+% test coverage, benchmark tests and godocs. Tested with go 1.9.
A collection of performant, concurrent safe, complex abstract data structures used for priority queues.
Priority queue is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority.
An O(1)/O(1+K) priority queue (very fast) implementation for small integers, that uses an assembly of N simple queues. It is optimized for large amount of data BUT with small value priorities ( <= 255 ). Can store any type of elements/values.
It is a modification of the Hierarchical Queue structure, adding some complexity (O(log n/k)) but removing it's limitations. With the right parameters can be fast, only 3-4 times slower than a HQ for 1M elements. Can store any type of elements/values.
Inspired by Cris L. Luengo Hendriks paper
A collection of basic abstract heap data structures.
Implicit Heap description example
Dynamic Min & Max Implicit heaps.
Insert (push) and remove min/max (pop) have O(log n) complexity. The keys are intand values can be any type interface{}.
A collection of simple graph data structures, used for academic purposes.
AdjacencyList description
AdjacencyList is a collection of unordered lists used to represent a finite graph. The graph is undirected with values on nodes and edges. A collection of simple graph data structures, used for academic purposes.
It is a AdjacencyList with 3 extra functions, that allow 1 direction edge control.
Package tree contains simple Tree implementations for academic purposes.
BST description
A basic implementation of a Binary Search Tree with nodes: key(int), value(interface{}).
A collection of simple linear data structres, that are not in the standard Go lib, built for academic purposes.
Stack description
Basic stack (FILO) using the builtin linked list, can store any type, concurrency safe, no size limit, implements Stringer.
Queue description
Basic queue (FIFO) using the builtin linked list, can store any type, concurrency safe (optional mutex), no size limit, implements Stringer.
MultiPivot uses a variant of the QuickSort algorithm with multiple pivots, splitting the arrays in multiple segments (pivots+1). It can be used to sort large arrays.