ВУЗ:
Составители:
99
На рисунке 37 изображено то же дерево, что и на рис. 36, но вместо
победителей в нём представлены проигравшие. Дополнительный узел с
номером 0 добавлен на вершине дерева для указания чемпиона турнира.
Заметим, что каждый ключ, кроме чемпиона, является проигравшим ров-
но один раз. Таким образом, каждый ключ появляется один раз в конце-
вом узле и один раз во внутреннем.
Рис. 37. Турнир, в котором показаны проигравшие, а не победители
На практике конечным узлам дерева на рис. 37 будут соответство-
вать весьма длинные записи, расположенные в памяти ЭВМ, а внутрен-
ним узлам – указатели на эти записи. Заметим, что Р-путевое слияние
требует ровно Р конечных и Р внутренних узлов – по одному в соседних
группах. Это наводит на мысль о возможности использования известных
эффективных методов распределения памяти.
Технология выбора с замещением может быть использована на пер-
вой фазе внешней сортировки при получении начальных отрезков, если
фактически выполнить Р-путевое слияние входных данных с самими со-
бой. В этом случае Р выбирается достаточно большим, чтобы заполнить,
по существу, всю внутреннюю память. Каждая запись при выводе заме-
щается очередной записью из исходных данных. Если у этой новой запи-
си ключ меньше ключа выведенной записи, то она не включается в теку-
щий отрезок. В противном случае она обычным образом включается в
дерево выбора и становится частью отрезка, порождаемого в данный мо-
мент. Таким образом, каждый отрезок может содержать больше Р запи-
сей, хотя в любой момент в дереве выбора находится не более Р записей.
Таблица 4 иллюстрирует описанный процесс для Р = 4. В ней числа,
заключённые в скобки, ожидают включения в следующий отрезок.
170
154
275
908
897
426
653
509
87
503
512
503
87
512
61
908
170
897
275
653
426
154
509
2
1
3
4 5 6 7
8 9 10 11 12 13 14 15
16 17 18 19 20 21 22 23
61
0
Страницы
- « первая
- ‹ предыдущая
- …
- 97
- 98
- 99
- 100
- 101
- …
- следующая ›
- последняя »
