Изменения

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