В главе 19 CLRS есть проблема 19-1, которая звучит следующим образом.
Профессор Пизано предложил следующий вариант процедуры FIB-HEAP-DELETE, утверждая, что она работает быстрее, когда удаляемый узел не является узлом, на который указывает H.min.
PISANO-DELETE(H, x)
if x == H.min
FIB-HEAP-EXTRACT-MIN(H)
else y = x.p
if y != NIL
CUT(H, x, y)
CASCADING-CUT(H, y)
add x's child list to the root list of H
remove x from the root list of H
c. Предположим, что мы называем PISANO-DELETE (H, x), и пусть H '- это куча Фибоначчи, которая получается. Предполагая, что узел x не является root, ограничьте потенциал H 'в терминах x.degree, c, t (H) и m (H).
В Решение онлайн: следующий ответ: ![enter image description here](https://i.stack.imgur.com/oA6uf.png)
Но я не совсем понимаю это. Я думаю, что число детей в H 'будет числом детей в H + 1, и число детей увеличится на то, что было у x. Это даст
Phi (H ') <= t (H) + x.degree + c + m (H) + 1 </p>