Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[141]

Сит(Я,ж,у)

1удалить х из списка детей вершины у, уменьшив degree[y] на 1

2добавить х в корневой список кучи Н

3р[х] <- nil

4mark[x] <- false

Cascading-Cut(#, у)

1z <r- p[y]

2if z ф nil

3then if mark[y] = false

4then mark[y] <- true

5else Сит(Я, y,z)

6Cascading-Cut(#, z)

Процедура Fib-Heap-Decrease-Key работает так. Сначала (строки 1-3) проверяется, действительно ли новое значение ключа меньше старого. Если да, то старое значение заменяется на новое. Возможно, новое значение по-прежнему больше значения в вершине-родителе, тогда всё в порядке. Если же нет, то в строках 6-7 поддерево с корнем х вырезается и переносится в корневой список с помощью процедур «каскадного вырезания».

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

Мы будем следить, чтобы у одной и той же вершины, не входящей в корневой список, не удалялось несколько детей. Для этого используются пометки (поле mark): после удаления ребёнка (перенесения его в корневой список с помощью процедуры Сит) вершина делается отмеченной, если она ранее не была отмеченной и не была корнем (строки 3-4 процедуры Cascading-Cut). Если же вершина, у которой удалён ребёнок, уже была отмеченной, то она сама переносится в корневой список, а для её родителя повторяется та же процедура.

После выполнения операций вырезания остаётся только скорректировать атрибут тгп[Н]. Заметим, что минимальной может быть либо вершина с уменьшенным ключом, либо прежняя минимальная вершина.

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


ке объединяются. При этом вершина может либо остаться в корневом списке, приобретя нового ребёнка (если её ключ меньше ключа другой вершины, с которой она объединяется), либо стать ребёнком другой вершины корневого списка. Вершина корневого списка может не только приобретать детей, но и терять их (процедура Сит); отметим, что при этом она не становится помеченной (строка 4 процедуры Cascading-Cut выполняется, лишь если выполнено условие в строке 2).

В какой-то момент вершина исключается из корневого списка, становясь ребёнком другой вершины при выполнении процедуры Consolidate. При этом её пометка (если она была) удаляется (строка 3 процедуры Fib-Link). С этого момента новых детей у неё не прибавляется, но может быть удалён один ребёнок, отчего она станет помеченной. При удалении второго ребёнка вершина вновь перемещается в корневой список, становясь непомеченной. Другой способ вернуться в корневой список - оказаться ребёнком изымаемой вершины при операции Fib-Heap-Extract-Min (при этом пометка не меняется).

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

На рис. 21.4 показаны две операции Fib-Heap-Decrease-Key, первая из которых не вызывает цепочки операций Сит, а вторая вызывает.

Покажем, что учётная стоимость операции Fib-Heap-Decrease-Key составляет 0(1). Начнем с определения фактической стоимости. Процедуры Fib-Heap-Decrease-Key, Сит и Cascading-Cut не содержат циклов, так что время работы пропорционально длине цепочки рекурсивных вызовов (которую мы обозначим через с).

Как при этом меняется потенциал? Цепочка рекурсивных вызовов соответствует цепочке помеченных вершин в дереве, каждая из которых является ребёнком следующей. Эти вершины перемещаются в корневой список и становятся непомеченными. Таким образом, потенциал увеличивается примерно на с за счёт увеличения числа вершин в корневом списке, но и уменьшается примерно на 2с за счёт того, что уменьшается число помеченных вершин. (Правда, может появиться новая помеченная вершина, но эта поправка имеет порядок 0(1).) В итоге потенциал уменьшается на с + 0(1). (Теперь ясно, почему при определении потенциала число помеченных вершин учитывалось со вдвое большим весом, чем число вершин в корневом списке!)

Умножая потенциал на достаточную константу (выбирая боль-


Рис. 21.4 Два вызова процедуры Fib-Heap-Decrease-Key. (а) Исходная фибоначчиева куча, (б) Ключ 46 уменьшается до 15, соответствующая вершина становится корневой, а её родитель (с ключом 24) - отмеченным, (в)-(д) Ключ 35 уменьшается до 5; вершина стала корневой (в). Её родитель (с ключом 26) был отмечен, так что его приходится также перенести в корневой список (г); затем то же самое происходит и с ключом 24. На этом каскад вырезаний заканчивается, так как вершина с ключом 7 - корневая. (Если бы она не была корневой, то она стала бы отмеченной, и каскад всё равно закончился бы.) После этого остаётся перенести указатель тгп[Н] на новую минимальную вершину (д).

шую «единицу работы»), можно считать, что уменьшение потенциала компенсирует фактическую стоимость цепочки рекурсивных вызовов, так что учётная стоимость операции Fib-Heap-Decrease-Key есть 0(1).

Удаление вершины

Эта операция сводится к двум рассмотренным ранее (мы считаем, что ключ -оо меньше всех ключей кучи).

Fib-Heap-Delete (Я, ж)

1Fib-Heap-Decrease-Key(#, ж, -оо)

2Fib-Heap-Extract-Min(#)

Аналогичным образом мы поступали и с биномиальными деревьями. Сначала вершина ж делается минимальной, а затем удаляется. Учётная стоимость таких действий равна сумме учётной сто-



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]