90
правок
Изменения
Нет описания правки
===Расход памяти===
При перераспределении и копировании HAT использует меньше памяти, чем в стандартных подходах. Самый плохой случай для HAT {{---}} размер элементов равен размеру указателей, и число элементов на один больше числа, при котором происходит расширение структуры(N=ResizeValue+1). Для этого случая значения приведены в таблице.Затраты памяти в самом плохом случае {{---}} <math>(top+leaf-1) ~= 2*\sqrt{N} = O(\sqrt{N})</math>. Если последний лист будет половиной полного, то ожидаемая трата памяти уменьшается до <math>(top + leaf/2) ~= 1.5*\sqrt{N}</math>, а это все еще <math>O(\sqrt{N})</math>.
Сравним с другими структурами, добавляющими элементы за <math>O(1)</math>. Например, отдельно связанные списки требуют O(N) памяти (один указатель для каждого элемента).
