212
правок
Изменения
м
→Основная идея
==Основная идея==
Будем развивать идею пирамидальной сортировки. Для этого будем использовать не двоичную кучу, а специальную, полученную с помощью чисел Леонардо<ref>[https://ru.wikipedia.org/wiki/%D0%A7%D0%B8%D1%81%D0%BB%D0%B0_%D0%9B%D0%B5%D0%BE%D0%BD%D0%B0%D1%80%D0%B4%D0%BE Википедия {{---}} Числа Леонардо]</ref>, которые задаются следующим образом:
<tex>
L(n):=
\begin{cases}
1 & :\mathrm{if } n = 0, \\ 1 & :\mathrm{if }n = 1, \\ L(n-1)+L(n-2)+1 & :\mathrm{if }n > 1. \\
\end{cases}
</tex>
