Изменения

Затраты дополнительной памяти (уже выделенной, но еще не используемой) в самом плохом случае {{---}} <tex>(top+leaf-1) ~= 2\sqrt{N} = O(\sqrt{N})</tex> (этот случай при пустой HAT {{---}} в <tex>top</tex> один указатель на единственный пустой лист).  Если в листе будет <tex>power/2</tex> элементов, то ожидаемая трата дополнительной памяти уменьшается до <tex>(top + leaf/2) \approx 1.5\sqrt{N}</tex>. Таким образом HAT использует <tex>\Theta(\sqrt{N})</tex> дополнительной памяти. Это лучше [[wikipedia:ru:Динамический массив |динамического массива]], который использует <tex>O(N)</tex> дополнительной памяти сразу после перекопирования элементов, и лучше [[wikipedia:ru:Список (информатика) |списка]].