Бинарная куча

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

Мы могли бы реализовать такую структуру с помощью простого массива, в котором приоритеты расположены по возрастанию, и вставлять новый приоритет в массив, сдвигая хвост массива так, чтобы он вновь был отсортирован. Ясно, что при вставке случайного приоритета, нам в среднем придётся сдвигать около половины массива, и операция вставки будет занимать время O(N). К счастью, специально для такой задачи существует структура данных под названием бинарная куча, которая позволяет извлекать и добавлять элементы за время O(log(N)).

Бинарная куча – это:

  1. Бинарное дерево (один корневой узел, у каждого узла не более двух дочерних узлов). В каждом узле хранится одно значение.
  2. В дереве должны быть заполнены до конца все уровни, кроме последнего. Если последний заполнен не полностью, его следует заполнять слева направо.
  3. Значение в каждом узле должно быть не меньше, чем в его дочерних узлах, если они есть.

Пример кучи показан на рисунке 1.

_images/heap01.png

Сразу же возникает вопрос: как хранить такое дерево в памяти компьютера, ведь она, как мы помним, линейна? Ответ на такой вопрос достаточно прост: мы можем уложить все элементы дерева по очереди в массив, начиная с верхнего уровня и располагая элементы одного уровня слева направо.

_images/heap02.png

При этом, из индекса родительского узла parent индексы дочерних получаются с помощью выражений (2 * parent + 1) и (2 * parent + 2). Обратное преобразование и для левых, и для правых дочерних узлов child даётся выражением (child - 1) // 2.

Если нужно добавить элемент в кучу, он добавляется на последнюю позицию нижнего уровня (или на новый уровень, если нижний заполнен). При этом вовсе не обязательно будет выполняться свойство 3. Чтобы оно выполнилось, мы обменяем местами вновь добавленный элемент и родительский элемент. Если после этого для новой позиции добавленного элемента вновь не выполняется свойство 3, мы вновь поменяем местами два элемента. И так надо повторять, пока родительский элемент не окажется больше добавленного, или мы не переместим новый элемент на верхний уровень. Пример на рисунке.

_images/heap03.png

Извлечение элемента происходит в несколько этапов:

  • Сохранение максимума (см. рис. 4.1) На верхнем уровне уже находится нужный нам максимальный элемент. Мы сразу же получаем результат, но так как сам элемент нужно удалить из кучи, над восстановлением свойств кучи придётся немного повозиться.
  • Перемещение последнего элемента кучи в вершину кучи (рис. 4.2). Крайний правый элемент нижнего уровня запишем в ячейку верхнего уровня и уменьшим размер кучи на 1, чтобы удалить ячейку, в которой он первоначально был (рис. 4.3). Как видно из рисунка, теперь он может нарушать третье свойство кучи.
  • Далее происходит “спуск” элемента по следующему правилу: на каждом этапе из двух дочерних ячеек текущей ячейки мы выбираем ту, в которой значение максимально. Если этот максимум больше значения текущей ячейки, мы обмениваем местами эти два значения. Таким образом мы восстановили свойство кучи для текущего уровня и спустились на уровень вниз. Эту операцию нужно повторять до тех пор, пока текущее значение не будет больше максимального из дочерних или до тех пор, пока не закончатся дочерние элементы (и значение не опуститься на нижний уровень).
_images/heap04.png