Двоичная куча — это тип бинарного дерева, который имеет свой собственный набор правил. Существует два типа двоичных куч: максимальная куча и минимальная куча.

Правила

Первое правило, которому следует бинарная максимальная куча, заключается в том, что значение каждого узла должно быть больше, чем значение всех его потомков. Это означает, что если узел, на который вы смотрите, имеет номер 8, все последующие узлы должны быть меньше 8. В двоичной минимальной куче значение каждого узла должно быть меньше значения всех его потомков. Как видите, правило меняется на противоположное в зависимости от типа создаваемой двоичной кучи.

Пример двоичной максимальной кучи

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

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

Вставка

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

Вставьте 45 в максимальную кучу

Квадрат здесь представляет собой крайнюю правую точку. Мы сравним 45 с его родителем 12. 45 больше 12, поэтому мы поменяем их местами.

Снова сравните 45 с его новым родителем 33. 45 больше, чем 33, поэтому мы поменяем их местами.

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

Удаление

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

Удалить 50 из максимальной кучи

Сначала замените 50 последним узлом в куче.

Квадрат показывает, что это позиция, из которой пришли 12, поскольку это был последний узел в куче.

Затем сравните 12 с его дочерними элементами 45 и 25. Мы поменяем местами 12 с 45, потому что это большее значение между двумя дочерними элементами.

Теперь сравните 12 с его новыми потомками 20 и 33. 33 — наибольшее значение, поэтому мы поменяем местами 33 и 12.

Теперь мы закончили, потому что у 12 больше нет детей.

Случай использования

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

Чтобы узнать больше о реализации бинарной кучи, ознакомьтесь с этой статьей GeeksforGeeks.