algorithms README

The project's README from github.com/keon/algorithms. As one markdown file: README.md.

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

Backtracking

Bit Manipulation

Compression

Dynamic Programming

Graph

Greedy

Heap

Linked List

Map

Math

Matrix

Queue

Searching

Set

Sorting

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

algorithms (keon/algorithms)

Searching Database…

25.6K ·GitHub
Algorithms
Что это такое?Это набор минималистичных, хорошо документированных реализаций классических структур данных и алгоритмов на Python 3. Его задача — читать и изучать код, а не использовать его как зависимость.
Это библиотека, которую нужно импортировать, или просто справочный код для чтения?Структура проекта похожа на пакет Python (есть примеры установки и использования), но его главная цель — учебный справочный код: в каждом файле есть docstring'и, аннотации типов и оценки сложности.
Как его запустить?Клонируйте репозиторий, установите его (в нём есть «Quick Start» с разделами «Install» и «Use»), затем запускайте или импортируйте нужные файлы с алгоритмами. Раздел «Project Structure» показывает, где что лежит.
Нужно ли что-то особенное установить заранее?Достаточно Python 3: в проекте не указано никаких внешних зависимостей времени выполнения.
Можно ли просто установить это через pip и использовать в боевом коде?Не совсем. Проект задуман как учебный материал: в нём простые минималистичные реализации, а не оптимизированная библиотечная версия, рассчитанная на продакшен.
Как организован репозиторий?Структуры данных находятся в algorithms/datastructures/, по одному модулю на каждую структуру (например, avltree.py, bst.py, heap.py). Алгоритмы сгруппированы по категориям (Array, Backtracking, Bit Manipulation, Compression, Dynamic Programming, Graph, Greedy, Heap, Linked List, Map и другие), каждая категория — набор коротких самостоятельных файлов.
Какие темы в нём рассматриваются?Охватываются структуры данных (AVL-деревья, красно-чёрные деревья, деревья отрезков и Фенвика, префиксные деревья, система непересекающихся множеств union-find, кучи, хеш-таблицы) и алгоритмы: поиск по графам (Dijkstra, A*, Bellman-Ford), задачи динамического программирования (например, задача о рюкзаке и расстояние редактирования), перебор с возвратом, битовые операции и схемы сжатия вроде Huffman и LZW.
Можно ли запустить тесты, чтобы проверить реализации?Да. В README есть отдельный раздел «Run Tests», а в проекте настроены рабочие процессы CI (python-app.yml) для автоматического тестирования.
Зачем использовать это вместо учебника?Каждая реализация короткая, самостоятельная и снабжена docstring'ами, аннотациями типов и оценками сложности. Поэтому конкретный алгоритм проще понять отдельно, чем продираться через целую главу учебника.
What are similar projects?javascript-algorithms, interactive-coding-challenges, JavaScript, hello-algo, algo, C-Plus-Plus, LeetCode-Go, gods
Which topics is it in?tree, algorithms-implemented, data-structure, sort, competitive-programming, leetcode, graph, algorithm, data-structures, interview-preparation, algorithms, search
Creator
keon
Size
2 MB
Stars
25.6K
Updated
CommitSep 25Releasev1.0.1Feb 18
Age
9y
Commits · 90 Days