Потенциальная функция из вопроса PISANO-DELETE в главе 19 CLRS - PullRequest
0 голосов
/ 26 февраля 2020

В главе 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

Но я не совсем понимаю это. Я думаю, что число детей в H 'будет числом детей в H + 1, и число детей увеличится на то, что было у x. Это даст

Phi (H ') <= t (H) + x.degree + c + m (H) + 1 </p>

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...