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