908 I I 170 I I 897 I 275 653 [426

Рис. 62. Турнир, в котором выбирается наименьший ключ; используется полное бинарное дерево, узлы которого пронумерованы от 1 до 23.

Рис. 63. Тот же турнир, что и на рис. 62, но показаны проигравшие, а не победители; чемпион находится на самом верху.

наводит на мысль, что мы в действительности должны записать во внутренние узлы проигравшего в каждом матче, а не победителя. Тогда информация, необходимая для изменения дерева, будет легкодоступной.

На рис. 63 изображено то же дерево, что и на рис. 62, но вместо победителей в нем представлены проигравшие. Дополнительный узел с номером "О" добавлен, на вершине дерева для указания чемпиона турнира. Заметим, что каждый ключ, кроме ключа чемпиона, является проигравшим ровно один раз (см. раздел 5.3.3).

На практике внешним узлам в нижней части рис. 63 будут соответствовать весьма длинные записи, расположенные в памяти компьютера, а внутренним узлам - указатели на эти записи. Заметим, что Р-путевое слияние требует ровно Р

внешних и Р внутренних узлов - по одному в соседних группах. Это наводит на мысль о возможности использовать известные эффективные методы распределения памяти. Нетрудно увидеть, каким образом можно применять дерево проигравших для выбора с замещением. Более детально мы обсудим этот алгоритм в настоящем разделе чуть позже.

Получение начальных серий посредством выбора с замещением. Технология выбора с замещением может использоваться на первой фазе внешней сортировки, если фактически вьшолнить Р-путевое слияние входных данных с самими собой. В этом случае Р выбирается достаточно большим, чтобы заполнить, по существу, всю внутреннюю память. Каждая запись при вьшоде замещается очередной записью из исходных данных. Если ключ новой записи меньше ключа выведенной записи, то мы не добавляем ее в текущую серию; в противном случае мы обычным образом включаем ее в дерево выбора, так что она образует часть серии, порождаемой в данный момент. Таким образом, каждая серия может содержать больше Р записей, хотя в любой момент в дереве выбора находится не более Р записей. В табл. 1 показан этот процесс для Р - i; числа, заключенные в скобки, ожидают включения в следующую серию.

Таблица 1

пример четырехпутевого выбора с замещением

Этот важный метод формирования начальных серий впервые был описан X. Г. Сьювордом [Е. Н. Seward, Masters Thesis, Digital Computer Laboratory Report R,-232 (Mass. Inst, of Technology, 1954), 29-30]. Он привел соображения в пользу того, что если применять метод к случайным данным, серии, видимо, будут содержать более 1.5Р записей. Ту же идею предложил примерно в 1950 году А. И. Думи (А. I. Dumey), который занимался разработкой в Engineering Research Associates специального устройства для сортировки, но не опубликовал ее. Само название "выбор с замещением" было придумано Э. Г. Фрейдом [Е. Н. Friend, JACM 3 (1956), 154], который заметил, что "ожидаемая длина порождаемой последовательности не поддается точной формулировке, но эксперименты позволяют предположить, что разумной оценкой будет 2Р".

Рис. 64. Вечный снегоочиститель в своем нескончаемом цикле.

Э. Ф. Мур (Е. F. Moore) предложил изящный способ доказательства того, что ожидаемая длина серии равна 2Р, проведя аналогию со снегоочистителем, движущимся по кругу [U.S. Patent 2983904 (1961), columns 3-4]. Рассмотрим ситуацию, изображенную на рис. 64: на кольцевую дорогу равномерно падают снежинки и один снегоочиститель непрерывно убирает снег. Снег исчезает из системы, как только он выбрасывается на обочину. Точки дороги обозначаются вещественными числами х, О < X < 1, снежинка, падающая в точку х, соответствует входной записи с ключом X, а снегоочиститель представляет собой вывод процесса выбора с замещением. Скорость снегоочистителя обратно пропорциональна весу снега, который встречается на его пути, и ситуация вполне уравновешена, так что общее количество снежинок на дороге в точности равно Р. Каждый раз, когда снегоочиститель проходит точку О, на выходе формируется новая серия.

Интуитивно ясно, что система, поработав некоторое время, выйдет на установившийся режим, при котором снегоочиститель будет двигаться с постоянной скоростью (в силу круговой симметрии дороги). Это означает, что в точке, в которой находится снегоочиститель, снег имеет постоянный вес, а впереди снегоочистителя этот вес линейно уменьшается, как показано на рис. 65. Отсюда следует, что количество снега, удаляемого за один оборот (а именно - длина серии), вдвое превосходит количество снега Р, присутствующего в любой момент.

Падающий снег

I I I I I I Ф ф ф М Ф

Рис. 65. Поперечное сечение, показывающее переменный вес снега перед снегоочистителем, когда система находится в установивщемся режиме.