Информатика · объяснение и практика

Почему двоичная куча выдаёт минимум без полной сортировки

Проверяем инвариант минимальной кучи, извлекаем корень из собственного массива и объясняем, почему оставшиеся элементы не обязаны идти по порядку.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Структуры данных · Учебная карта

Главная мысль

В минимальной двоичной куче значение родителя не больше значений его детей. Поэтому минимум находится в корне. Но между соседними поддеревьями полного порядка нет: куча обеспечивает быстрый выбор минимума, а не готовый отсортированный массив.

Что гарантирует форма и что гарантируют значения

Рассмотрим массив [2,7,4,9,8,6]. При нулевой индексации дети позиции i находятся на позициях 2i+1 и 2i+2, если такие существуют. Корень 2 не больше 7 и 4; родитель 7 не больше 9 и 8; родитель 4 не больше 6. Значит, инвариант минимальной кучи выполнен.

При этом массив не отсортирован: 7 стоит перед 4, а 8 перед 6. Это допустимо. Двоичная куча имеет форму заполненного по уровням слева направо дерева. Такая форма удерживает высоту логарифмической; одно лишь правило «родитель меньше детей» без ограничения формы не даёт той же оценки операций.

Пример

Минимум массива-кучи равен 2, хотя следующий по величине элемент 4 расположен правее 7.

Для выдачи минимума не требуется сравнивать все соседние позиции между собой: достаточно цепочек отношений от корня к потомкам.

Как убрать корень и сохранить структуру

Извлечём 2. Чтобы не оставить дырку в начале, перенесём последний элемент 6 в корень и сократим массив. Получится [6,7,4,9,8]. Теперь 6 больше ребёнка 4, поэтому меняем их местами. Итог [4,7,6,9,8] снова удовлетворяет правилу кучи.

При просеивании вниз выбирают меньшего из существующих детей. Обмен с произвольным ребёнком может оставить нарушение у другого. Для вставки новый элемент сначала ставят в конец, затем поднимают, пока он меньше родителя. На каждом шаге меняется положение вдоль одной цепочки дерева, остальные связи остаются корректными.

Какие вопросы куча решает и не решает

Посмотреть минимум можно сразу по корню, извлечение и вставка требуют порядка логарифма количества элементов. Но поиск произвольного числа не получает такой же гарантии: инвариант не говорит, в каком именно поддереве оно лежит. Для частого поиска по ключу нужна другая структура или дополнительный индекс.

В очереди задач часто сравнивают приоритеты, а не содержимое самих задач. Если равные приоритеты должны выходить в порядке поступления, добавляют отдельный возрастающий номер: стабильность не возникает автоматически. Изменение приоритета уже лежащего элемента также требует восстановления инварианта; простая правка числа в середине массива способна испортить последующее извлечение. Пустую очередь обрабатывают отдельно до чтения корня.

От чтения к действию

А теперь — вы

Какой массив является корректной минимальной кучей при нулевой индексации?

Частые вопросы

Нужно ли сортировать массив перед построением кучи?

Нет: кучу можно построить непосредственно. Сортировка тоже даёт допустимую минимальную кучу в массивном представлении, но делает больше работы, чем требуется только для построения.

Можно ли взять второй элемент массива как второй минимум?

Нет: второй минимум находится среди детей корня, но это может быть правый ребёнок. В примере это 4, а на позиции 1 хранится 7.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться