algorithm - 关于二项式队列性能

Question

以下文字来自二项式队列文章。

尽管 leftist 和 skew heaps 在每次操作 O(log n) 时间内都有效地支持合并、插入和 delete_min，但仍有改进的余地，因为我们知道二进制堆支持每次操作的平均时间不变的插入。二项式队列在每个操作的最坏情况时间 O(log n) 内支持所有三个操作，但插入平均花费恒定时间。

在上面的文字中，作者所说的每次操作的平均时间不变是什么意思？它与二项式队列插入平均需要恒定时间有何不同？

每次操作的恒定平均时间和平均恒定时间之间有什么区别？

Answer 1

每次操作的恒定平均时间和平均恒定时间之间有什么区别？

没有区别。作者一方面对比了左倾堆和倾斜堆，另一方面对比了二叉堆，以表明二叉堆具有左倾堆和倾斜堆所没有的二叉堆的一些优点（预期 O(1) 插入）（他们只有摊销的O(1) 插入）。