time-complexity - 插入操作如何在二项式堆中具有 O(1) 的摊销时间？

Question

维基百科说二项式堆中的插入操作的摊销时间为 O(1)。对于单个插入操作，时间复杂度为 O(log n)。但是它的摊销时间如何变成 O(1) 呢？

Answer 1

当您的根列表具有等级为 1、2、3、...、m（中间没有缺失）的树时，单个插入操作仅需要 log n 时间，其中 m 是最大树的等级。每个二项式堆的根列表都可以表示为一个二进制数。如果二项式堆看起来像 11111 并且您插入一个节点，那么它将变为 100000。但是，您在接下来的几次插入节点时不会有那么多进位。