Я сейчас реализую кучу Фибоначчи в соответствии с исходной Бумагой Фредмана и Тарьяна.Если я правильно понимаю, согласно статье, для выполнения операции DecreseKey узла x , мы просто отсекаем его от его родителя.Но если ключ после уменьшения все еще больше, чем его родитель, он будет неэффективным (я думаю).Кроме того, я вижу много проектов, которые обрезают узел только тогда, когда его ключ становится меньше, чем его родительский, как в CLRS.
Так что я немного запутался в его оригинальном дизайне.Почему они не применили более эффективный способ сделать DecreaseKey .Или, может быть, это облегчает амортизированный анализ?Любой ответ приветствуется.Заранее спасибо.