data-structures

Data structures in Go

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.

!! Warning This library wasn't used in production (yet). !!

priorityqueue

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.

Hierarchical Queue description

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.

Hierarchical Heap

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

heap

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{}.

graph

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.

AdjacencyListDirected

It is a AdjacencyList with 3 extra functions, that allow 1 direction edge control.

tree

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{}).

linear

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.

Multi-Pivot QuickSort

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.