"Куча" по сравнению с Двоичными деревьями - Как реализовать?

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

В основном потому, что рекурсивное дерево допускает очень простой код. Если вы превратите дерево в массив, код станет действительно сложным, потому что вам придется выполнять много бухгалтерских операций, которые рекурсивный алгоритм делает за вас.

Кроме того, дерево высотой N может иметь что угодно от N до 2 ^ (N + 1) -1 узлов (. Память потребуется только фактическим узлам. Если вы используете массив, вы должны всегда выделяйте место для всех узлов (даже пустых), если вы не используете разреженный массив (что сделало бы код еще более сложным). Таким образом, хотя сохранить разреженное дерево высотой 100 в памяти легко, было бы проблематично найдите компьютер, который может выделить 20282409603651670423947251286008 байт ОЗУ.

Если позиция всех детей является статически предварительно докомпоренным, то, то массив существенно представляет собой полностью полное, полностью сбалансированное бинарное дерево.

Не все двоичные деревья в «реальной жизни» совершенно полны и идеально сбалансированы. Если вы должны иметь несколько особенно длинных ветвей, вам нужно было бы сделать весь ваш массив намного больше, чтобы разместить все узлы на нижнем уровне.

• Если бинарное дерево, связанное с массивом в основном пустым, большая часть пространства массива потрачена впустую.

• Если только некоторые из ветвей деревьев достаточно глубоки, чтобы добраться до «дна» массива, также есть много места впустую.

• Если дерево (или только одна ветвь) необходимо вырастить «глубже», чем размер массива, позволит вам потребует «растущий» массив, который обычно реализуется как копирование в более широкий массив. Это дорогое время.

Итак: Использование указателей позволяет нам динамически расти структуру и гибко. Представление дерева в массиве - это хорошее академическое упражнение и хорошо работает для небольших и простых случаев, но часто не выполняет требования «реальных» вычислений.

Лично

1. , потому что используя указатели легче расти размер структуры данных динамически

2. Я считаю, что легче поддерживать корзину Дерево, чем куча

3. Алгоритмы баланса, удаления, вставки элементов в дереве будут изменить только указатели и не перемещаться тогда физически как в векторе.

И так далее ...

в первом примере выполняется неявный вызов конструктора копирования

A<bool>(A<bool> const&)

во втором примере. поэтому компилятор должен использовать шаблонный конструктор для создания нового объекта провозглашение

 template <typename T2>
A(A<T2>const& val){
    cout<<sizeof(val.dummmyField)<<endl;
}

должно прояснить это

Чтобы вставить элемент в кучу, можно поместить его в любое место и заменить родительским элементом до тех пор, пока ограничение кучи снова не станет действительным. Swap-with-parent - это операция, которая сохраняет двоичную древовидную структуру кучи нетронутой. Это означает, что куча размером N будет представлена в виде массива N-ячеек, и можно добавить новый элемент за логарифмическое время.

Двоичное дерево поиска может быть представлено в виде массива размером N с использованием той же структуры представления, что и куча (потомки 2n и 2n + 1), но вставка элемента этого пути намного сложнее, поскольку в отличие от ограничения кучи, ограничение двоичного дерева поиска требует выполнения поворотов для извлечения сбалансированного дерева. Таким образом, либо вам удается сохранить дерево N-узлов в массиве N-ячеек по цене выше логарифмической, либо вы тратите пространство, сохраняя дерево в большем массиве (если моя память служит, красное дерево может тратить до 50% вашего массива).

Таким образом, двоичное дерево поиска в массиве интересно только в том случае, если данные внутри являются постоянными. И если это так, то вам не нужна структура кучи (children 2n и 2n + 1): вы можете просто отсортировать свой массив и использовать двоичный поиск .

Реализация на основе массива полезна, если требуется куча, которая используется в качестве приоритетной очереди в алгоритмах графов. В этом случае элементы в куче являются постоянными, при этом появляется самый верхний элемент и вставляются новые элементы. Удаление верхнего элемента (или min-элемента) требует некоторой повторной балансировки, чтобы снова стать кучой, что может быть сделано так, чтобы массив был достаточно сбалансирован.

Эталоном для этого является алгоритм Голдберга и Тарьяна об эффективном вычислении оптимального сетевого потока в направленных графиках, iirc.

Чтобы вставить элемент в кучу, вы можете поместить его где угодно и поменять его со своим родителем, пока ограничение кучи снова не будет действительным. Swap-S-родитель - это операция, которая сохраняет двоичную древесную структуру кучи Initact. Это означает, что куча размера n будет представлена ​​как массив N-клеток, и вы можете добавить новый элемент в логарифмическом времени.

Двоичное дерево поиска может быть представлена ​​в виде массива размера N, используя одну и ту же структуру представления в качестве кучи (детей 2n и 2n + 1), но вставляя элемент таким способом намного сложнее, потому что в отличие от ограничения кучи, Двоичное ограничение деревьев поиска требует выполнения вращений для извлечения сбалансированного дерева. Итак, либо вам удается сохранить дерево N-узла в массиве N-клеток по затратам выше, чем логарифмические, или вы тратите пространство, сохраняя дерево в более широком массиве (если моя память служит, красно-обратное дерево может отходы до 50% вашего массива).

Итак, двоичное дерево поиска в массиве интересна только в том случае, если данные внутри постоянны. И если это так, то вам не нужна структура кучи (детей 2n и 2n и 2n + 1): вы можете просто сортировать свой массив и использовать двоичный поиск .