What is a Heap?
Урок 2 из 14 курса Кучи и очереди с приоритетом — Структуры данных №7 на Coddy.
Куча — это древовидная структура данных, которая подчиняется одному простому инварианту: каждый родитель меньше (или равен) своих потомков. Наименьшее значение всегда находится в корне, готовое к чтению за O(1). Эта конкретная разновидность называется min-heap (минимальная куча); зеркальное отображение с инвариантом «наибольшее в корне» — это max-heap (максимальная куча).
Хитрость заключается в способе хранения. Хотя мы представляем её как дерево, куча располагается в плоском массиве. Для узла с индексом i:
- Его родитель находится по индексу
(i - 1) / 2. - Его левый потомок находится по индексу
2 * i + 1. - Его правый потомок находится по индексу
2 * i + 2.
Никаких указателей, никаких объектов узлов: только математика индексов. Это делает кучи очень эффективными для кэша и простыми в реализации.
Пять основных операций над min-heap:
- Peek: Возвращает наименьшее значение (корень).
- Insert: Добавляет значение и поднимает его («всплытие») на нужное место.
- ExtractMin: Удаляет и возвращает наименьшее значение.
- Size: Возвращает количество хранящихся значений.
- IsEmpty: Проверяет, пуста ли куча.
Давайте создадим класс MinHeap!
Попробуйте сами
В этом уроке нет задания по программированию.
