Структуры данных

Функция len() в Python — один из самых часто используемых инструментов. Она возвращает количество элементов в объекте: длину строки, списка, словаря и других коллекций. Но как она работает под капотом? Почему для одних объектов она выполняется мгновенно, а для других может вызвать ошибку? В этой статье разберемся с внутренней реализацией len() и её особенностями. В основе функции len() лежит магический метод __len__(), который должен быть реализован в объекте. Когда вы вызываете len(obj), интерпретатор Python автоматически обращается к obj...

Поиск кратчайшего пути — одна из ключевых задач в теории графов, имеющая множество практических применений: от маршрутизации в навигационных системах до искусственного интеллекта в играх. В этой статье мы рассмотрим основные алгоритмы поиска кратчайшего пути и их реализацию на Python. Когда использовать: Ненагруженные графы (без весов на рёбрах). Принцип работы: Алгоритм исследует все узлы на текущей глубине перед переходом на следующий уровень. Гарантирует нахождение кратчайшего пути по количеству шагов...

Куча (heap) — это специализированная структура данных, которая представляет собой почти полное бинарное дерево, удовлетворяющее свойству кучи. В Python для работы с кучами используется модуль heapq, реализующий минимальную кучу (min-heap), где родительский элемент всегда меньше или равен дочерним. Это позволяет эффективно получать и удалять минимальный элемент. В статье рассмотрим, как использовать кучу в Python, основные операции и примеры применения. 1. Минимальная куча: Корневой элемент — наименьший в дереве...

Стек — это структура данных, работающая по принципу LIFO (Last In, First Out), где последний добавленный элемент извлекается первым. В Python стек можно реализовать разными способами, и в этой статье мы рассмотрим основные методы, примеры кода и практическое применение. Стандартный список в Python идеально подходит для реализации стека. Для этого используются два метода: - push() → append(): добавление элемента в конец списка. - pop(): удаление и возврат последнего элемента. Пример: Для удобства можно создать класс, инкапсулирующий логику стека: - Push: Добавление элемента на вершину стека...

Дерево — это иерархическая структура данных, состоящая из узлов, связанных отношениями «родитель-потомок». Каждое дерево имеет корневой узел (root), от которого происходят все остальные элементы. Деревья широко применяются в программировании для представления иерархий (например, файловая система), алгоритмах поиска, машинном обучении и синтаксическом анализе. В Python деревья можно реализовать с помощью классов, рекурсии и стандартных библиотек. - Корень (Root): Начальный узел дерева. - Узел (Node): Элемент дерева, который может содержать данные и ссылки на дочерние узлы...

Графы — одна из ключевых структур данных в computer science, используемая для моделирования связей между объектами. В этой статье мы разберем два основных алгоритма обхода графов (BFS и DFS), их реализацию на Python и практическое применение. Граф состоит из вершин (узлов) и ребер (связей между ними). Он может быть: - Направленным (ребра имеют направление) - Ненаправленным (ребра без направления) - Взвешенным (ребрам присвоены значения) - Невзвешенным Пример представления графа в Python через список смежности: Принцип работы: Послойный обход, начиная от стартовой вершины...