берем в качестве границы некоторую функцию (3(к), определённую для неотрицательных целых к. Мы предполагаем, что функция fi является монотонно возрастающей и что fi(k) > к при всех к. Будем говорить, что при переходе от вершины и к её родителю v = р[и] ранг сильно растёт, если rank[v] fi(rank[u]). При этом мы исключаем из рассмотрения случай, когда v является корнем - такой случай встречается по разу при выполнении каждой операции Find-Set, и потому общее число таких ситуаций есть О (га).

Начнём с оценки числа шагов, при которых ранг не сильно растёт, и сгруппируем их по вершинам, из которых этот шаг делается. Для вершины ранга к ранги её предка могут меняться от к + 1 до fi(k) (после этого ранг растёт сильно). Значит, число таких шагов (из данной вершины ранга к) заведомо не больше fi(k), поскольку, как мы говорили, каждый новый шаг ведёт в вершину большего ранга, чем предыдущий. Поскольку вершин ранга к не более п/2к, то общее число шагов, при которых ранг не сильно растёт, не превосходит

Если выбрать функцию fi так, чтобы ряд fi{k)/2к сходился, то общее число шагов такого рода есть О (га).

Прежде чем выбрать функцию fi, объясним, как оценить число шагов, при которых ранг сильно растёт. Такие шаги мы сгруппируем не по вершинам, а по путям: на каждом пути поиска таких шагов мало, так как ранг не может многократно сильно расти (он меняется всего лишь от 0 до lgra). Таким образом, на каждом пути число шагов, при котором ранг сильно растёт, не превосходит числа итераций функции fi, которые нужно сделать, чтобы дойти от 0 до lg га.

Хотелось бы положить fi{k) = 2к: тогда число итераций будет примерно равно lg* га. К сожалению, тогда написанный выше ряд расходится. Придётся взять немного меньшую функцию. Напри-

мер, положим fi{k) = [l,9fc], тогда ряд Y[l,9fc]/2fc Y(l,9fc + l)/2fc

сходится. С другой стороны, число итераций функции fi, которые нужно сделать, чтобы от 0 дойти до какого-то числа, возрастёт (по сравнению с функцией к н-> 2к) не более чем вдвое, поскольку fi(fi(k)) 2к, и потому есть 0(lg*ra). Итак, число шагов такого рода для всех га операций есть 0(ralg*ra).

Складывая вместе действия всех видов (операции Make-Set и Link, последние шаги в каждом пути, шаги, на которых ранг не сильно растёт, и шаги, на которых ранг сильно растёт), получаем общую оценку О (га) +0(ralg*ra) = 0(ralg*ra) (напомним, что га га, так как га - общее число операций, ага - число операций textscMake-Set), что и требовалось доказать.

[Замечание. Доказательство этой теоремы слегка изменено по

к

сравнению с английским оригиналом: в последнем используется функция (3(к), равная наименьшему члену последовательности 1, 2, 4,16, 65536,..., большему к (каждый член последовательности есть двойка в степени предыдущего члена). Тогда на каждом пути будет не более lg* га шагов, на которых ранг сильно растёт, а ряд Y fi(k)/2к сходится, но имеет достаточно медленно растущие частичные суммы.]

Из доказанной теоремы и леммы 22.6 немедленно вытекает

Следствие 22.8

Предположим, что над системой непересекающихся множеств (изначально пустой) произвели то операций Make-Set, Find-Set и Union, га из которых- Make-Set. Тогда при использовании реализации с помощью леса со сжатием путей и объединением по рангам стоимость этой последовательности операций есть 0(m\g* п).

Упражнения

22.4-1

Докажите лемму 22.2. 22.4-2

Сколько битов нужно, чтобы хранить sizefa:] для узла ж? Тот же вопрос для гапк[х]. 22.4-3

Пользуясь леммой 22.2 и следствием 22.5, докажите, что стоимость то операций с лесом непересекающихся множеств с использованием объединения по рангам, но без сжатия путей, есть О (то lgra), где га, как обычно, обозначает количество операций Make-Set.

22.4-4*

Объясните, почему последние шаги путей требовали в нашем рассуждении особого рассмотрения (а на классифицировались в зависимости от роста ранга, как все остальные): приведите пример ситуации, в которой некоторая вершина ж входит Г2(то) раз в путь поиска для операции Find-Set, причём при выходе из неё ранг растёт не сильно. (Как видно из доказательства, это возможно лишь если она по большей части является предпоследней вершиной пути.)

Задачи

22-1 Поиск минимума в режиме off-line.

Задача о поиске минимума в режиме off-line (off-line minimum problem) состоит в следующем. Пусть имеется динамическое множество Г, поддерживающее операции Insert) (добавить элемент ж) и Extract-Min (удалить минимальный элемент). Первоначально множество Г пусто, затем выполняется некоторая последовательность из га операций Insert и то операций Extract-Min, причем операции Insert добавляют в множество по одному разу все натуральные числа от 1 до га (не обязательно в порядке возрастания). Требуется по данной последовательности операций In-

sert(a;) и Extract-Min создать массив extracted[l..m], в котором extracted[i] - число, возвращаемое г-ой по счёту операцией Extract-Min.

Говоря о «режиме off-Нпе», имеют в виду, что от нас требуется дать ответ после того, как мы знаем всю последовательность команд (в противоположность этому, в режиме «оп-line» от нас требовалось бы давать ответ немедленно по поступлении очередной команды, не дожидаясь следующей).

(а)Пусть команды поступали в такой последовательности (мы пишем Е вместо Extract-Min и г вместо Insert(z)):

4,8,Е,3,Е,9,2,6,Е,Е,Е, 1,7,Е,5.

Как выглядит массив extracted?

Алгоритм для решения задачи о минимуме в режиме off-line может выглядеть следующим образом. Пусть S - данная последовательность команд. Представим ее в виде

Ii, Е, I2, Е, 13,..., Im, Е, Im+i,

где каждое Е обозначает операцию Extract-Min, а каждое L- обозначает последовательность операций Insert (возможно, пустую). Для каждой последовательности L- создадим множество Kj, состоящее из чисел, добавляемых в Г при операциях Insert из последовательности lj. А теперь сделаем вот что:

Off-Line-Minimum(m,n)

1for i \gets 1 to n

2do найти такое $j$, что $i\in K j$

3if j \ne m+l

4then extracted[j] \gets i

51 \gets (наименьшее число, большее $j$,

для которого существует множество $К 1$)

6K l\gets K l\cup K j (множество $K j$ исчезает)

7return extracted

(б)Покажите, что алгоритм Off-Line-Minimum правильно заполняет массив extracted.

(в)Реализуйте алгоритм Off-Line-Minimum с помощью системы непересекающихся множеств. Дайте достаточно точную оценку времени работы в худшем случае.

22-2 Определение глубины

В задаче определения глубины (depth-determination problem) требуется реализовать лес Т, состоящий из корневых деревьев Гг-, поддерживающий следующие три операции:

Make-Tree(u) Создает новое дерево с единственной вершиной v.