Skip to content

keon/algorithms

PyPI version Open Source Helpers

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 coin_change

# Minimum coins to make amount 29 using denominations [1, 5, 10, 25]
print(coin_change([1, 5, 10, 25], 29))
# 7   (25 + 1 + 1 + 1 + 1)

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

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
  • 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