ВУЗ:
Составители:
97
17. МНОГОПУТЕВОЕ СЛИЯНИЕ И
ВЫБОР С ЗАМЕЩЕНИЕМ
Расширим понятие двухпутевого слияния до понятия Р-путевого
слияния, когда Р входных отрезков объединяются в один выходной.
Пусть имеется Р возрастающих отрезков, т.е. последовательностей
записей, ключи которых расположены в неубывающем порядке. Очевид-
ным способом их слияния будет следующий: посмотреть на первые запи-
си каждого отрезка и выбрать из них ту, которой соответствует мини-
мальный ключ; эта запись передаётся на выход и исключается из вход-
ных данных, затем процесс повторяется.
Пока Р не слишком велико, этот выбор удобно осуществлять, просто
выполняя Р – 1 сравнений для нахождения наименьшего из текущих
ключей. Но если, скажем, Р ≥ 8, то можно сократить работу, используя
дерево выбора (см. параграф 13). При этом каждый раз требуется только
приблизительно log
P сравнений (после начального формирования дере-
ва). Рассмотрим, например, четырёхпутевое слияние с двухуровневым
деревом выбора:
Шаг 1 87
∞
∞
∞
∞
612154
653426
154
908170
50387
87
Шаг 2 87 154
∞
∞
∞
∞
612154
653426
154
908170
503
170
Шаг 3 87 154 170
∞
∞
∞
∞
612
653426
426
908170
503
170
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Шаг 9 87 154 170 426 503 612 653 908 ∝
∞
∞
∞
∞
∞
∞
Страницы
- « первая
- ‹ предыдущая
- …
- 95
- 96
- 97
- 98
- 99
- …
- следующая ›
- последняя »
