algorithms
Minimal, clean, and well-documented implementations of data structures and algorithms in Python 3.
Each file is self-contained with docstrings, type hints, and complexity notes — designed to be read and learned from.
Quick Start
Install
pip install algorithms
Use
from algorithms.sorting import merge_sort
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]
from algorithms.data_structures import BinaryHeap, Trie, BST
from algorithms.graph import dijkstra, bellman_ford
from algorithms.tree import TreeNode
Examples
Graph — Dijkstra's shortest path:
from algorithms.graph import dijkstra
graph = {
"s": {"a": 2, "b": 1},
"a": {"s": 3, "b": 4, "c": 8},
"b": {"s": 4, "a": 2, "d": 2},
"c": {"a": 2, "d": 7, "t": 4},
"d": {"b": 1, "c": 11, "t": 5},
"t": {"c": 3, "d": 5},
}
print(dijkstra(graph, "s", "t"))
# (8, ['s', 'b', 'd', 't'])
Dynamic programming — coin change:
from algorithms.dynamic_programming import count
# Number of ways to make amount 10 using denominations [2, 5, 3, 6]
print(count([2, 5, 3, 6], 10))
# 5
Backtracking — generate permutations:
from algorithms.backtracking import permute
print(permute([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
Data structures — binary heap:
from algorithms.data_structures import BinaryHeap
heap = BinaryHeap()
for val in [5, 3, 8, 1, 9]:
heap.insert(val)
print(heap.remove_min()) # 1
print(heap.remove_min()) # 3
Searching — binary search:
from algorithms.searching import binary_search
print(binary_search([1, 3, 5, 7, 9, 11], 7))
# 3 (index of target)
Tree — inorder traversal:
from algorithms.tree import TreeNode
from algorithms.tree import inorder
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)
print(inorder(root))
# [1, 2, 3, 4, 6]
String — Knuth-Morris-Pratt pattern matching:
from algorithms.string import knuth_morris_pratt
print(knuth_morris_pratt("abxabcabcaby", "abcaby"))
# 6 (starting index of match)
Run Tests
python -m pytest tests/
Project Structure
algorithms/
data_structures/ # Reusable data structure implementations
array/ # Array manipulation algorithms
backtracking/ # Constraint satisfaction & enumeration
bit_manipulation/ # Bitwise operations & tricks
compression/ # Encoding & compression schemes
dynamic_programming/ # Optimal substructure & memoization
graph/ # Graph algorithms (BFS, DFS, shortest path, flow, ...)
greedy/ # Greedy strategies
heap/ # Heap-based algorithms
linked_list/ # Linked list algorithms
map/ # Hash-map-based algorithms
math/ # Number theory, combinatorics, algebra
matrix/ # 2D array & linear algebra operations
queue/ # Queue-based algorithms
searching/ # Search algorithms (binary, linear, ...)
set/ # Set-based algorithms
sorting/ # Sorting algorithms
stack/ # Stack-based algorithms
streaming/ # Streaming & sketching algorithms
string/ # String matching, manipulation, parsing
tree/ # Tree algorithms (traversal, BST ops, ...)
tests/ # One test file per topic
Data Structures
All core data structures live in algorithms/data_structures/:
| Data Structure |
Module |
Key Classes |
| AVL Tree |
avl_tree.py |
AvlTree |
| B-Tree |
b_tree.py |
BTree |
| Binary Search Tree |
bst.py |
BST |
| Fenwick Tree |
fenwick_tree.py |
Fenwick_Tree |
| Graph |
graph.py |
Node, DirectedEdge, DirectedGraph |
| Hash Table |
hash_table.py |
HashTable, ResizableHashTable |
| Heap |
heap.py |
BinaryHeap |
| KD Tree |
kd_tree.py |
KDTree |
| Linked List |
linked_list.py |
SinglyLinkedListNode, DoublyLinkedListNode |
| Priority Queue |
priority_queue.py |
PriorityQueue |
| Queue |
queue.py |
ArrayQueue, LinkedListQueue |
| Red-Black Tree |
red_black_tree.py |
RBTree |
| Segment Tree |
segment_tree.py, iterative_segment_tree.py |
SegmentTree |
| Separate Chaining Hash Table |
separate_chaining_hash_table.py |
SeparateChainingHashTable |
| Sqrt Decomposition |
sqrt_decomposition.py |
SqrtDecomposition |
| Stack |
stack.py |
ArrayStack, LinkedListStack |
| Trie |
trie.py |
Trie |
| Union-Find |
union_find.py |
Union |
| vEB Tree |
veb_tree.py |
VEBTree |
Algorithms
Array
- delete_nth — keep at most N occurrences of each element
- flatten — recursively flatten nested arrays into a single list
- garage — minimum swaps to rearrange a parking lot
- josephus — eliminate every k-th person in a circular arrangement
- limit — filter elements within min/max bounds
- longest_non_repeat — longest substring without repeating characters
- max_ones_index — find the zero to flip for the longest run of ones
- merge_intervals — combine overlapping intervals
- missing_ranges — find gaps between a low and high bound
- move_zeros — move all zeros to the end, preserving order
- n_sum — find all unique n-tuples that sum to a target
- plus_one — add one to a number represented as a digit array
- remove_duplicates — remove duplicate elements preserving order
- rotate — rotate an array right by k positions
- summarize_ranges — summarize consecutive integers as range tuples
- three_sum — find all unique triplets that sum to zero
- top_1 — find the most frequently occurring values
- trimmean — compute mean after trimming extreme values
- two_sum — find two indices whose values sum to a target
Backtracking
Bit Manipulation
Compression
- elias — Elias gamma and delta universal integer coding
- huffman_coding — variable-length prefix codes for lossless compression
- lzw_compression — dictionary-based Lempel-Ziv-Welch compression
- rle_compression — run-length encoding for consecutive character compression
Dynamic Programming
Graph
Greedy
Heap
Linked List
Map
Math
Matrix
Queue
Searching
Set
Sorting
- bead_sort — gravity-based natural sorting (bead/abacus sort)
- bitonic_sort — parallel-friendly comparison sort via bitonic sequences
- bogo_sort — random permutation sort (intentionally inefficient)
- bubble_sort — repeatedly swap adjacent out-of-order elements
- bucket_sort — distribute elements into buckets, then sort each
- cocktail_shaker_sort — bidirectional bubble sort
- comb_sort — bubble sort improved with a shrinking gap
- counting_sort — sort integers by counting occurrences
- cycle_sort — in-place sort that minimizes total writes
- exchange_sort — simple pairwise comparison and exchange
- gnome_sort — sort by swapping elements backward until ordered
- heap_sort — sort via a binary heap (in-place, O(n log n))
- insertion_sort — build a sorted portion one element at a time
- meeting_rooms — determine if meeting intervals overlap
- merge_sort — divide-and-conquer stable sort (O(n log n))
- pancake_sort — sort using only prefix reversals
- pigeonhole_sort — sort by placing elements into pigeonhole buckets
- quick_sort — partition-based divide-and-conquer sort
- radix_sort — non-comparative sort processing one digit at a time
- selection_sort — repeatedly select the minimum and swap it forward
- shell_sort — generalized insertion sort with a decreasing gap sequence
- sort_colors — Dutch national flag three-way partition
- stooge_sort — recursive sort by dividing into overlapping thirds
- wiggle_sort — rearrange into an alternating peak-valley pattern
Stack
Streaming
String
Tree
Contributing
Thanks for your interest in contributing! There are many ways to get involved. See CONTRIBUTING.md for details.
Maintainers
Contributors
Thanks to all the contributors who helped build this repo.
License
MIT
这是一组用 Python 3 编写的经典数据结构与算法实现，代码精简、注释详尽，供阅读和学习，而不是作为依赖项来使用。