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