Изменения

Получение последовательности Последовательность куч, для которых не выполняется инвариант, очевидно производится за <tex dpi = 120> O(N) </tex>. По указанному выше утверждению <tex dpi = 120> N </tex> можно представить получается последовательной вставкой элементов массива в виде суммы длин кучконец. Пусть <tex dpi = 120> N = L(k_1) + L(k_2) + ... + L(k_n) </tex>, тогда выполнение операции '''heapify''' для всех куч выполнится за <tex dpi = 120> O(L(k_1)) + O(L(k_2)) + ... + O(L(k_n)) = O(N) </tex>. В итоге построение последовательности выполняется за Получаем время работы <tex dpi = 120> O(N) + O(N) + O(\log^2{N}) = O(N) </tex>.

===Лучший случай===Однако если подать на вход плавной сортировке уже отсортированный массив, асимптотика будет составлять <tex dpi = 120> O(N) </tex>. Дело в том, что операция :*Операция добавления элемента последовательности на таком примере будет выполняться за <tex dpi = 120> O(1) </tex>, из-за того, что в конец будет добавляться максимальный элемент и просеивание будет сразу останавливаться.*Операция получения и удаления максимального элемента будет так же выполняться за <tex dpi = 120> O(1) </tex>, потому что в силу построения в корнях куч-детей будут новые максимальные элементы и следовательно восстановление свойства последовательности закончится на просмотре корня соседней кучи. В итоге на таком примере получается асимптотика <tex dpi = 120> O(N) </tex>.