76
правок
Изменения
→Обработка блока: Ещё дополнил
В итоге, обработка блока делится на следующие этапы:
* Достаем из очереди <tex>B</tex> ключи <tex>x</tex>, конвертируем их в элементы <tex>\mathtt{elt}(x)</tex> и кладём в список <tex>\mathtt{elems}</tex>.
* Сливаем элементы в <tex>\mathtt{elems}</tex> со следующим отсортированным блоком <tex>C_j^s</tex> в список <tex>\mathtt{merged}</tex>.* Присваиваем новые ключи элементам , генерируя два вспомогательных массива <tex>\mathtt{ind_0}</tex> и <tex>\mathtt{ind_1}</tex>, хранящих индексы элементов списков <tex>C_j^s</tex> и <tex>\mathtt{elems}</tex> соответственно в порядке списка списке <tex>\mathtt{merged}</tex> и находим ключи в порядке исходной последовательности, действуя .* Действуя на последовательность ключей в сортированном блоке списке <tex>\mathtt{ind_0}</tex> перестановкой <tex>\xi</tex>получим ключи в порядке исходной последовательности.* Вставляем в <tex>B</tex> новые ключи элементовсписка <tex>\mathtt{elems}</tex> (элементы <tex>\mathtt{ind_1}</tex>).
* Обрабатываем ключи элементов блока в порядке исходной последовательности с помощью алгоритма <tex>\mathrm{LIS}</tex>. Для восстановления НВП также используем массив "предшественников", который будет работать с соответствующими ключам элементами <tex>\mathtt{elt}(x)</tex>.
