212
правок
Изменения
→Операции над последовательностью куч
==Операции над последовательностью куч==
При конструировании последовательности куч будем последовательно выполнять вставку в конец новых элементов, а при операции получении отсортированного массива будем удалять максимальный элемент из последовательности. Следовательно , нам необходимы две операции: увеличение последовательности куч путём добавления элемента справа (будем считать, что последовательность начинается кучами самого большого размера) и уменьшение путём удаления крайнего правого элемента (корня последней кучи), с сохранением состояния кучи и последовательности.
Чтобы быстро обращаться к кучам, будем хранить список их длин.
# Крайняя правая куча (сформированная последней) считается «текущей» кучей.
# Пока слева от неё есть куча, и значение её корня больше значения текущего корня и обоих корней куч-потомков:
#* Меняются местами новый корень и корень кучи слева (что не нарушит свойство это гарантирует выполнение инварианта для текущей кучи). Эта И куча , с которой произошел обмен, становится текущей.# Выполняется Потом выполняется «просеивание»кучи, на которой остановилась сортировка корней, чтобы выполнялось свойство гарантировать выполнение инварианта кучи:
#* Пока размер текущей кучи больше <tex dpi = 120> 1 </tex>, и значение корня любой из куч-потомков больше значения корня текущей кучи:
#** Меняются местами наибольший по значению корень кучи-потомка и текущий корень. Куча-потомок становится текущей кучей.
Операция просеивания значительно упрощена благодаря использованию чисел Леонардо, так как каждая куча либо будет одноэлементной, либо будет иметь двух потомков. Нет нужды беспокоиться об отсутствии одной из куч-потомков.
Так как в последовательности <tex dpi = 120> O(\log{N}) </tex> куч и просеивание можно выполнить , то модификация сортировки вставками будет работать за <tex dpi = 120> O(\log{N}) </tex>. Просеивание тоже выполняется за <tex dpi = 120> O(\log{N}) </tex>, то время тогда в итоге операция вставки получаетсявыполняется за:
<tex dpi = 120> O(\log{N}) + O(\log{N}) = O(\log{N}) </tex>.
