76
правок
Изменения
м
Простым проходом по отсортированному Находим последовательность ключей, соответствующую элементам блоку <tex>C_j^s</tex> находим последовательность ключей, соответствующую его элементам. Действуя на эту последовательность перестановкой <tex>\xi_j</tex>, получаем последовательность ключей в порядке исходного блока.
→Обработка блока
В итоге, получим отсортированный список <tex>\mathtt{merged}</tex>. Сопоставим ключ каждому элементу как его позицию в этом списке, тогда справедливы утверждения, что <tex>\mathtt{elt}(x)=\mathtt{merged}[x]</tex> и <tex>(\pi_{i}<\pi_{k} \Longleftrightarrow \mathtt{key}(\pi_{i})<\mathtt{key}(\pi_{k}))</tex>, где <tex>\pi_{i},\pi_{k}\in \mathtt{merged}</tex>, поэтому любая возрастающая последовательность ключей элементов будет соответствовать возрастающей последовательности элементов. Таким образом, приоритетная очередь сможет корректно работать с ключами элементов.
Оставшиеся ключи, которые входят в <tex>\mathtt{merged}</tex>, но не являются ключами элементов в обрабатываемом блоке , будут ключами элементов из очереди <tex>B</tex>. Обновляем очередь <tex>B</tex> этими ключами.
Затем запускаем алгоритм <tex>\mathrm{LIS}</tex>, для ключей элементов <tex>C_j</tex> в порядке исходной последовательности.
