此外，分析将显示在最初执行 N 次插入 最坏情况下，空二项式队列将花费 O(N) 时间。事实上，仅使用 N-1 次比较就可以完成此操作；我们将此作为练习。
我在一本数据结构书中读到了这一点。我知道插入平均需要恒定的时间，在最坏的情况下需要 O(log n)。我无法理解该声明在说什么。
最佳答案
在插入操作期间，每次比较后都会合并两棵树(要插入的节点是 0 阶树)。合并操作会使树的总数减少1，并且任何操作都不会 split 树或增加树的数量。
因此，从 N 个单独的节点开始，即 N 个 0 阶树，如果我们进行 N-1 比较，那么我们将进行N-1合并，并且仅留下1树。此时不可能进一步合并，因此最多需要 N-1 次比较。
关于algorithm - 在 N-1 比较中，如何在最初为空的二项式队列中插入 N 个元素？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/49598102/