Data Structures and Algorithms in Rust

Some interesting data structures and algorithms implemented in Rust. Docs are hosted here.

Testing

The doctests are very slow, so you can run test.py to copy all doctests into src/tests.rs and run them. This makes them run around 100x faster.

TODO

Most entries on this list were taken directly from Keith Schwarz's Archive of Interesting Code and TODO list.

	Name	File	Description
✅	Binary Heap	src/heap.rs	A priority queue implementation backed by a binary heap.
✅	Topological Sort	src/toposort.rs	An algorithm for finding a topological ordering of a DAG.
✅	Graph	src/graph.rs	An implementation of a weighted graph.
✅	Directed Graph	src/digraph.rs	An implementation of a weighted, directed graph.
✅	VList	src/vlist.rs	A dynamic array implementation backed by a VList.
✅	Immutable Vector	src/ivector.rs	An immutable vector implementation with efficient edits/clones.
✅	Interval Heap	src/iheap.rs	An implementation of a double-ended priority queue backed by an interval heap.
✅	Quickselect	src/quickselect.rs	An implementation of the quickselect algorithm.
✅	Union-Find	src/unionfind.rs	An implementation of a disjoint-set data structure using a disjoint set forest.
✅	Insertion Sort	src/insertion_sort.rs	An implementation of the insertion sort algorithm.
✅	Radix Sort	src/radix_sort.rs	An implementation of the radix sort algorithm.
✅	Quicksort	src/quicksort.rs	An implementation of the quicksort algorithm.
✅	Mergesort	src/mergesort.rs	An implementation of the merge sort algorithm.
✅	Heapsort	src/heapsort.rs	An implementation of the heapsort algorithm.
❌	Timsort	TODO	An implementation of the Timsort algorithm.
✅	MJRTY	src/mjrty.rs	A fast, linear-time algorithm for finding the majority element of a data set.
✅	Bidirectional Map	src/bimap.rs	An implementation of a bidirectional map.
✅	Bump Allocator	src/bumpalloc.rs	A bump allocator.
❌	Quickhull	TODO	An implementation of the quickhull algorithm.
✅	Binomial Heap	src/binomialheap.rs	A priority queue implementation backed by a binomial heap.
❌	Extendible Array	TODO	A dynamic array implementation with O(1) worst-case lookup and append.
❌	Hashed Array Tree	TODO	A dynamic array implementation backed by a hashed array tree.
✅	Fibonacci Heap	src/fibheap.rs	A priority queue implementation backed by a Fibonacci heap.
❌	Dijkstra's Algorithm	TODO	An implementation of Dijkstra's algorithm for single-source shortest paths.
❌	Prim's Algorithm	TODO	An implementation of Prim's algorithm for finding minimum spanning trees.
❌	Kruskal's Algorithm	TODO	An implementation of Kruskal's algorithm for finding minimum spanning trees.
✅	Levenshtein Distance	src/levenshtein.rs	An implementation of the Wagner–Fischer algorithm for finding the Levenshtein distance between two slices.
✅	Bloom Filter	src/bloom.rs	An implementation of a Bloom filter.
❌	Cuckoo Map	TODO	An associative array implementation using cuckoo hashing.
❌	Treap	TODO	A sorted associative array implementation backed by a treap.
❌	Floyd-Warshall Algorithm	TODO	An implementation of the Floyd-Warshall algorithm for all-pairs shortest paths in a graph.
❌	Edmonds's Matching Algorithm	TODO	An implementation of Edmonds's matching algorithm for finding maximum matchings in undirected graphs.
✅	Fenwick Tree	src/fenwick.rs	A Fenwick tree implementation.
✅	DiGraph Cycles	src/cycle.rs	An algorithm for finding cycles in a directed graph.
❌	Kosaraju's Algorithm	TODO	An implementation of Kosaraju's algorithm for finding strongly connected components of a directed graph.
❌	Bellman-Ford Algorithm	TODO	An implementation of the Bellman-Ford algorithm for single-source shortest paths.
✅	Graham's Scan	src/graham.rs	An implementation of Graham's scan for finding convex hulls in 2D space.
❌	Johnson's Algorithm	TODO	An implementation of Johnson's algorithm for all-pairs shortest paths.
❌	Deflate	TODO	An implementation of the Deflate algorithm
✅	Ring Buffer-Backed Deque	src/deque.rs	An implementation of a deque using a ring buffer.
❌	Rabin-Karp Algorithm	TODO	An implementation of the Rabin-Karp algorithm for string matching.
✅	Any Stack	src/anystack.rs	An implementation of a stack that can contain values of any type
✅	Min-Stack	src/minstack.rs	An implementation of a LIFO stack that supports O(1) push, pop and find-minimum.
✅	Min-Queue	src/minqueue.rs	An implementation of a FIFO queue that supports O(1) push, pop and find-minimum.
❌	Suffix Automaton	TODO	An implementation of a suffix automaton.
❌	Fortune's Algorithm	TODO	Fortune's algorithm for generating Voronoi diagrams.
✅	Median Heap	src/medianheap.rs	A data structure for efficiently calculating a running median.
❌	Aho–Corasick Algorithm	TODO	An implementation of the Aho–Corasick algorithm for string-searching.
❌	Soft Heap	TODO	A soft heap implementation.
❌	Link/Cut Tree	TODO	A link/cut tree implementation.
❌	Rope	TODO	An implementation of a rope for efficient string manipulation.
❌	GADDAG	TODO	A GADDAG implementation.
❌	Burrows–Wheeler Transform	TODO	An implementation of the Burrows-Wheeler transform.
❌	Seam Carving	TODO	An implementation of the seam carving algorithm.
❌	Bounded Priority Queue	TODO	An implementation of a priority queue with a fixed upper limit to its size.
❌	Fast Fourier Transform	TODO	An implementation of the fast Fourier transform algorithm.
❌	Brodal Queue	TODO	A Brodal queue implementation for use as a priority queue.
❌	Chan's Algorithm	TODO	An implementation of Chan's algorithm.
❌	Christofide's Algorithm	TODO	An implementation of Christofide's algorithm for approximating TSP solutions.
✅	Trie	src/trie.rs	A trie implementation.
❌	Radix Tree	TODO	A radix tree implementation.
❌	Ukkonen's Algorithm	TODO	An implementation of Ukkonen's algorithm for constructing suffix trees.
❌	k-d Tree	TODO	A k-d tree implementation.
❌	Finger Tree	TODO	A finger tree implementation.
❌	Interval Tree	TODO	An interval tree implementation.
❌	Hough Transform	TODO	An implementation of the Hough transform.
❌	BSP Tree	TODO	An implementation of a BSP tree.
❌	Pairing Heap	TODO	A pairing heap implementation.
❌	Fusion Tree	TODO	An associative array implementation backed by a fusion tree.
❌	Push–Relabel Algorithm	TODO	An implementation of the push–relabel maximum flow algorithm.
❌	Apostolico–Giancarlo Algorithm	TODO	An implementation of the Apostolico–Giancarlo algorithm.
❌	PQ Tree	TODO	A PQ tree implementation.
❌	Bitap Algorithm	TODO	An implementation of the bitap algorithm.
❌	NFA	TODO	An implementation of a nondeterministic finite automaton.
❌	DFA	TODO	An implementation of a deterministic finite automaton.
❌	NFA to DFA Conversion	TODO	An implementation of the subset construction algorithm for conversion from NFA to DFA.
❌	Polygon Triangulation	TODO	TODO
❌	Planarity Testing	TODO	TODO