47
правок
Изменения
м
→Пример
|}
|}
<tex>\mathtt{merged}</tex> аналогичен сортированному, т.к. предыдущих ключей нет.
{| class="wikitable" style="center"
! colspan="5"|Ключи сортированного блока
| 4||1||5||2||3
|}
Пропускаем их через <tex>\mathrm{LIS}</tex>:
{| class="wikitable" style="center"
|-align="center"
<tex>B: \{1, 2, 3\}</tex>
<tex>\mathtt{merged}: \{3, 4, 8, 9, 10\}</tex>
===== Второй блок =====
Восстанавливаем элементы <tex>B: \{1, 2, 3\}</tex> из <tex>\mathtt{merged}: \{3, 4, 8, 9, 10\}</tex>: <tex>\{3, 4, 8\}</tex>.
{|
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="8"|<tex>\mathtt{merged}</tex>
|-align="center"
| 1||2||3||4||5||6||8||12
{| class="wikitable" style="center"
|-align="center"
| colspan="3"|<tex>\mathtt{ind's\#0}</tex> — индексы текущих
|-align="center"
| 3||4||7
{| class="wikitable" style="center"
|-align="center"
| colspan="5"|<tex>\mathtt{ind's\#1}</tex> — индексы новых
|-align="center"
| 1||2||5||6||8
| 1||2||5||4||3
|}
Восстанавливаем порядок новых из <tex>\mathtt{ind's\#1}</tex> и <tex>\xi</tex>:
{| class="wikitable" style="center"
! colspan="5"| новые ключи
| 3 || 4 || style="background:#FFCC00"| 7 || style="background: #77A9F4"| 7
|}
<tex>\mathrm{LIS}</tex> новых:
{| class="wikitable" style="center"
|-align="center"
<tex>B: \{1, 2, 5, 8\}</tex>
<tex>\mathtt{merged}: \{1,2,3,4,5,6,8,12\}</tex>
===== Третий блок =====
Восстанавливаем элементы <tex>B: \{1, 2, 5, 8\}</tex> из <tex>\mathtt{merged}: \{1,2,3,4,5,6,8,12\}</tex>: <tex>\{1, 2, 5, 12\}</tex>.
{|
| ||
{| class="wikitable" style="center"
|-align="center"
| colspan="8"|<tex>\mathtt{merged}</tex>
|-align="center"
| 1||2||5||7||11||12
{| class="wikitable" style="center"
|-align="center"
| colspan="4"|<tex>\mathtt{ind's\#0}</tex> — индексы текущих
|-align="center"
| 1||2||3||6
{| class="wikitable" style="center"
|-align="center"
| colspan="2"|<tex>\mathtt{ind's\#1}</tex> — индексы новых
|-align="center"
| 4||5
| 1||2
|}
Восстанавливаем порядок новых из <tex>\mathtt{ind's\#1}</tex> и <tex>\xi</tex>:
{| class="wikitable" style="center"
! colspan="2"| новые ключи
<tex>B: \{1, 2, 3, 4, 5\}</tex>
<tex>\mathtt{merged}: \{1,2,5,7,11,12\}</tex>
===== Восстановление НВП =====
{| class="wikitable" style="center"
! colspan="12"| <tex>\mathtt{predecessor}</tex>
|-align="center"
| 1||2||3||4||5||6||7||8||9||10||11||12
| ||1|| ||3||2||2||5||4|| ||3||7||8
|}
Начинаем восстановление с <tex>\mathtt{merged}[5] = 11</tex>:
{| class="wikitable" style="center"
|+ обратный порядок
