имости операции Fib-Heap-Decrease-Key (которая есть 0(1)) и операции Fib-Heap-Extract-Min (которая есть 0(D(n))).

Упражнения

21.3-1 Каким образом может появиться помеченная вершина в корневом списке?

21.3-2 Докажите оценку 0(1) для учётной стоимости операции Fib-Heap-Decrease-Key, используя метод группировки (раздел 18.1).

21.4. Оценка максимальной степени

Для получения обещанных оценок О (lgra) для учётной стоимости операций Fib-Heap-Extract-Min и Fib-Heap-Delete осталось показать, что максимальная степень D(n), которую может иметь какая-либо вершина в фибоначчиевой куче с га вершинами, не превосходит О (lgra).

Как показывает упражнение 21.2-3, если все деревья в фибоначчиевой куче являются неупорядоченными биномиальными деревьями, то D(n) = [lgraJ- Но операции вырезания, которые происходят во время исполнения процедуры Fib-Heap-Decrease-Key, приводят к тому, что деревья в фибоначчиевой куче более не являются биномиальными. Мы покажем, что тем не менее при выполнении описанных операций остаётся в силе оценка D(n) = 0(lg2ra). Точнее, мы установим, что D(n) 1°8у п\ > гДе V = (1 + л/5)/2.

Для каждой вершины фибоначчиевой кучи через size (ж) обозначим число вершин в поддереве с корнем ж, считая саму вершину ж. (Вершина ж не обязана быть корневой вершиной кучи.) Мы покажем, что величина size(a:) экспоненциально зависит от degree[x]. (Напомним, что поле degree[x] поддерживается равным степени вершины ж.)

Лемма 21.1. Пусть ж - произвольная вершина фибоначчиевой кучи, и пусть degree[x] = к. Тогда степени к детей вершины ж не меньше О, 0,1, 2, 3,..., к - 2, если их расположить в надлежащем порядке.

Доказательство. Для вершин, не входящих в корневой список, определим «модифицированную степень», которая на единицу больше реальной степени для помеченных (и совпадает с ней для непомеченных). Смысл этого такой: поскольку при удалении ребёнка у вершины делается пометка, то её модифицированная степень не меняется, а добавление детей возможно только для вершин в корневом

списке. Таким образом, модифицированная степень есть степень на момент (последнего) выбытия вершины из корневого списка.

Поскольку модифицированная степень отличается от реальной не более чем на 1, достаточно доказать, что у вершины (реальной) степени к дети имеют модифицированную степень не менее 0,1, 2,..., к - 1. Ясно, что это свойство сохраняется при удалении одного из детей. Кроме того, оно сохраняется при добавлении к вершине степени к другой вершины степени к (при подчинении одной вершины корневого списка другой первая делается непомеченной, так что её реальная степень равна модифицированной).

□

Теперь оценим число потомков для вершины степени к, используя числа Фибоначчи. Напомним, что к-е число Фибоначчи Fk определяется так:

Оесли к = О,

Fk = < 1если к = 1,

Ffc i + Ffc 2 если к 2.

Лемма 21.2.

для любого к > 0.

к

Fk+2 = 1 + V F

8 = 0

Доказательство. При к = 0 это верно: 1 + Y=o Fi = 1 + Fq = 1 + 0 = 1 = F2.

Рассуждая по индукции, предполагаем, что Fk+\ = 1 + YZo F-Тогда

k-i

Fk+2 = Fk + Fk+1 = Fk+ l 1 + JFi =1 + X>8.

8 = 0 /8 = 0

□

Теперь мы уже можем оценить число вершин в поддереве, если известна степень его корня. Напомним, что Fk+2 к\ где f = (1 + у/5)/2 = 1.61803... - «золотое сечение» (2.14). (Это неравенство доказано в упр. 2.2-8.)

Лемма 21.3. Пусть х - вершина фибоначчиевой кучи, имеющая степень к или больше. Тогда size(a;) Fk+2 ipk, где ip = (1 + а/5)/2.

Доказательство. По лемме 21.1 вершина х имеет среди своих детей вершины степени не менее 0, 0,1, 2, 3,..., к - 2. Рассуждая по индукции, мы можем считать, что для детей доказываемое утверждение верно. (При к = 0 число Fk+2 равно 1 и оценка очевидна.)

Задачи к главе 21

437

Складывая число вершин в поддеревьях и прибавляя саму вершину ж, получаем, что

she(x) > (F2 + F2 + F3 + F4 + ... + Fk) + 1 = = (F0 + Fi + F2 + ... + Fk) + 1 = Fk+2

(мы используем равенство Fo + F\ = F2 и лемму 21.2).□

Следствие 21.4. Максимальная степень D(n) какой-либо вершины в фибоначчиевой куче с га вершинами есть О (lgra).

Доказательство. Пусть х - произвольная вершина такой кучи и пусть k = degree[x]. По лемме 21.3 имеем га size(a:) ipk, остаётся взять логарифм по основанию (р.

□

Упражнения

21.4-1 Профессор утверждает, что высота фибоначчиевой кучи из га элементов не превышает О (lgra). Покажите, что он ошибается и что существует последовательность операций рассмотренных нами типов, которая приводит к куче, состоящей ровно из одного дерева, являющегося линейной цепью из га вершин.

21.4-2 Изменим правила и будем считать, что вершина перемещается в корневой список, когда она потеряла к своих потомков, где к - некоторая константа (до сих пор мы считали, что к = 2). При каких значениях к можно утверждать, что D(n) = O(lgra)?

Задачи

21-1 Другой способ удаления элемента

Профессор предложил следующий вариант процедуры Fib-Heap-Delete, утверждая, что новая процедура работает быстрее в том случае, когда удаляемая вершина - не минимальная.

New-Delete(#, х)

1if х = тгп[Н]

2then Fib-Heap-Extract-Min (Я)

3else у <- р[х]

4if у ф nil

5then Сит(Я, ж, у)

6Cascading-Cut, у)

7добавить детей вершины ж в корневой список кучи Я

8удалить ж из корневого списка кучи Я