Куча (Heap) — это полное бинарное дерево, в котором каждый родительский узел меньше (в min-heap) или больше (в max-heap) своих дочерних узлов. Куча хранится в виде массива.
Соответствие массива и дерева (индексация с 0):
Родитель узла i: Math.floor((i - 1) / 2)
Левый потомок узла i: 2 * i + 1
Правый потомок узла i: 2 * i + 2
Операции:
insert: добавить в конец, поднять вверх (bubble up) — O(log n)
extractMin: удалить корень, опустить вниз (bubble down) — O(log n)
peek: вернуть корень — O(1)
Применение:
- Очереди с приоритетом
- Пирамидальная сортировка (Heap Sort)
- Алгоритм Дейкстры
- Поиск k-го наименьшего или наибольшего элемента
Похожие алгоритмы
Частые вопросы
- Что такое Куча (минимальная куча)?
- Куча (Heap) — это полное бинарное дерево, в котором каждый родительский узел меньше (в min-heap) или больше (в max-heap) своих дочерних узлов. Куча хранится в виде массива.
- Какова сложность Куча (минимальная куча)?
- Куча (минимальная куча) объясняется с помощью пошаговой визуализации, включая временную и пространственную сложность.
- Для кого предназначена визуализация Куча (минимальная куча)?
- Визуализация Куча (минимальная куча) рассчитана на средний уровень в категории «Структуры данных». Полезна для студентов, подготовки к собеседованиям и практического изучения.
- Какие алгоритмы связаны с Куча (минимальная куча)?
- В той же категории (Структуры данных) вы можете изучить: Stack, Queue, Linked List. Каждый из них имеет интерактивную визуализацию.