Как операция вставки имеет амортизированное время O(1) в биномиальной куче?

Question

Википедия говорит, что операция вставки в биномиальной куче имеет амортизированное время O(1). Для одной операции вставки временная сложность составляет O(log n). Но как его амортизированное время становится O(1)?

Answer 1

Одна операция вставки занимает только log n времени, когда в корневом списке есть деревья рангов 1, 2, 3, ..., m (ни одно не пропущено между ними), где m - ранг самого большого дерева. Корневой список каждой биномиальной кучи может быть выражен двоичным номером. Если биномиальная куча выглядит как 11111 и вы вставляете узел, тогда она становится 100000. Но у вас не будет такого количества переносов в следующие несколько раз, когда вы вставите узлы.