Почему двоичная куча лучше как массив, чем дерево?
При создании двоичной максимальной кучи, почему лучше реализовать ее как основанную на массиве, а не древовидную структуру (в основе дерева, как и в каждом node, также имеющий указатель на нее родительский)?
С точки зрения анализа времени выполнения, использования памяти, производительности...
Для двоичной максимальной кучи время выполнения:
- insert: O (lg n)
- удалить мин: O (lg n)
- merge: O (n)
Для реализации дерева
- insert: O (lg n)
- удалить мин: O (lg n)
- merge: O (n)
Может ли кто-нибудь объяснить подробно?
Ответы
Ответ 1
Дерево использует больше времени и памяти. Сложности одинаковы, но постоянные факторы различны.
Указатели дерева используют большую память, по сравнению с массивом на основе массива, где вам едва нужно какое-либо дополнительное пространство, кроме того, что оно берется самими значениями. И манипулирование этими указателями требует времени. Выделение и освобождение узлов может занять некоторое время и пространство...
Кроме того, нет гарантии, что узлы дерева будут объединены в памяти. Если какой-либо из двух альтернатив использует кеш, это куча массива.
Ответ 2
Со ссылкой на то, что уже было сказано через ответы других, можно задаться вопросом, почему мы не используем массивы и для BST. Двоичная куча требует, чтобы это было полное двоичное дерево. Поэтому глубина листовых узлов всегда h или h-1. Я считаю, что это свойство делает использование массивов идеальным для двоичных кучи и непригодным для BST (поскольку BST не имеет требования к полному двоичному дереву - оно может быть строгим/полным/полным).
