90
правок
Изменения
Нет описания правки
Чаще всего при добавлении элемента в одном из листьев (последнем незаполненном на данный момент) найдется свободное место, что позволит осуществить быструю вставку(<math>O(1)</math>).
Реже мы столкнемся со случаем, когда необходимо создать новый лист. Достаточно всего лишь добавить указатель в свободную ячейку главного массива, что также позволит произвести вставку элемента за <math>O(1)</math>.
Самый интересный случай {{---}} когда главный массив и все листья заполнены. Cначала вычислим нужный размер (массивы Top <tex>top</tex> и Leaf имеют тот же самый размер<tex>leaf</tex> увеличиваются в 2 раза, оба в степени то есть <math>power = power \cdot 2</math>), затем скопируем элементы в новую структуру HAT, освобождая старые листья и распределяя новые листья(размер листа изменился, а значит количество элементов в листе и количество используемых листьев так же изменится).Такой подход к расширению помогает избежать избыточного перекопирования, используемого во многих реализациях массивов переменной длины, потому что увеличения размеров всех массивов происходит редко (как будет видно ниже). Копировать элементы мы будем только тогда, когда главный массив полон(достигли соответствующей степени двойки). Например, для <tex> N=4^k </tex>(<tex>k </tex> {{--- }} натуральное число), общая сумма перекопирования будет равна <math>1+4+16+64+256+...+N</math>. Воспользуемся тождеством: <math>(x^{n+1} -1)=(x-1)(1+x+x^2+x^3+... + x^k)</math>, тогда для нашего случая: <math>1 +4+4^2+4^3+...+4^k = (4^{k+1} -1)/(4-1) = (4N-1)/3</math>, или около <math>4N/3</math>. Это означает, что среднее число дополнительных операций копирования {{- --}} <math>O(N)</math> для последовательного добавления N элементов, а не <math>O(N^2)</math>. Мы получили <math>4N/3</math> против <math>2N</math> в обычном динамическом массиве, то есть константа уменьшилась.
===Расход памяти===
При перераспределении и копировании HAT использует меньше дополнительной памяти, чем в стандартных подходах. Самый плохой случай для HAT {{---}} размер элементов равен размеру указателей, и число элементов на один больше числа, при котором происходит расширение структуры(<tex>N=ResizeValue+1</tex>). Для этого случая значения приведены в таблице.
Затраты доролнительной памяти в самом плохом случае {{---}} <math>(top+leaf-1) ~= 2\sqrt{N} = O(\sqrt{N})</math>. Если последний лист будет половиной полного, то ожидаемая трата дополнительной памяти уменьшается до <math>(top + leaf/2) \approx 1.5\sqrt{N}</math> (top {{---}} главный массив, leaf {{---}} листья), а это все еще <math>O(\sqrt{N})</math>.
Сравним с другими структурами, добавляющими элементы за <math>O(1)</math>. Например, отдельно связанные списки требуют O(N) дополнительной памяти (один указатель для каждого элемента).
