Ключевое различие между двоичной кучей и биномиальной кучей состоит в том, как структурированы кучи.В двоичной куче куча представляет собой одно дерево, которое представляет собой полное двоичное дерево.В биномиальной куче куча представляет собой коллекцию деревьев меньшего размера (то есть лес деревьев), каждое из которых является биномиальным деревом.Полное двоичное дерево может быть построено для хранения любого количества элементов, но количество элементов в биномиальном дереве некоторого порядка n равно всегда 2 n .Следовательно, нам нужно только одно полное двоичное дерево для резервного копирования двоичной кучи, но нам может потребоваться несколько биномиальных деревьев для резервного копирования биномиальной кучи.Интересно, что порядки биномиальных деревьев, используемых в биномиальной куче, соответствуют 1 битам, установленным в двоичном представлении числа элементов в лесу.
Причина организации биномиальных куч в том виде, в каком они есть, заключается в том, чтобиномиальное дерево порядка n всегда содержит ровно 2 n узлов.Это позволяет нам делать предположения о количестве элементов в биномиальном дереве без фактической проверки структуры этого дерева.С другой стороны, полное двоичное дерево некоторой высоты h может иметь переменное число узлов в нем в зависимости от того, как заполнена последняя строка.Тот факт, что каждый из дочерних элементов должен иметь очень точно определенную структуру, также может быть использован для доказательства того, что число дочерних элементов не превышает O (log n), где n - общее количество узлов в куче, что означает, чтостоимость delete-min не слишком велика.
Важной деталью этого является то, что биноминальная куча не любого дерева, в котором есть k дочерних элементов.Это дерево строго определено как
- Биномиальное дерево порядка 0 - это один узел, а
- Биномиальное дерево порядка n - это один узел с биномиальными деревьями порядка 0, 1, 2, ..., n - 1 как дети.
(Технически, особый случай порядка 0 здесь не нужен).Вы можете увидеть это здесь:
Обратите внимание, что существует точно одно дерево каждого ордера, без какой-либо гибкости в количестве или позицииузлы.
Однако важным альтернативным определением является следующее:
- Биномиальное дерево порядка 0 - это один узел, а
- Биномиальное дерево порядкаn - это два биномиальных дерева порядка n - 1, причем одно из них стало дочерним для другого.
(найдите минутку, чтобы понять, почему они эквивалентны).Используя это второе определение, можно быстро доказать, что число узлов в дереве равно 2 n .В качестве базового случая, дерево порядка 0 имеет 2 0 = 1 узел по мере необходимости.Для индуктивного шага, если у нас есть два дерева порядка n - 1, они вместе имеют 2 n-1 + 2 n-1 = 2 n узловкак требуется.Таким образом, общее количество узлов в биномиальном дереве порядка n равно 2 n .
Идея кучи, которую вы описываете в своем последнем абзаце, не всегда приводит кэффективное время выполнения.В частности, если у вас есть деревья с огромным коэффициентом ветвления и без других структурных ограничений, то теоретически вы можете построить кучу из n узлов, состоящих из одного узла с (n - 1) дочерними элементами.В этом случае после удаления минимального элемента из кучи вам нужно будет просмотреть все n - 1 дочерних элементов, чтобы определить, какой был новый минимум, и дать время выполнения O (n).Другие структурные ограничения на деревья, такие как полные двоичные деревья, биномиальные деревья и т. Д., Гарантируют, что этот наихудший случай не произойдет.
Надеюсь, это поможет!