有没有办法用n个给定元素构建一个二项式堆，最坏情况复杂度低于O（n log n），即使用n个连续插入？（我知道插入的摊销成本是 O(1)，因此构建的平均时间复杂度更小。）对于二叉堆，有一个更有效的构建实现，它将所有 n 个元素放在二叉树中并执行 heapify/siftDown在元素的前半部分以相反的顺序。只是想知道：二项式堆是否存在类似的聪明东西？
问问题
924 次
1 回答
2
实际上，将所有 n 个值插入堆中只需要 O(n) 时间。尽管二项式堆插入的最坏情况运行时间为 O(log n)，但平均而言它低于此值。
这是使用摊销分析看到这一点的一种方式。在二项式堆中的每棵树上放置一个信用。每当您进行插入时，如果它涉及将 k 个不同的树合并在一起，则实际运行时间是 Θ(1 + k)。在此过程中，我们还将花费 k 个积分，每棵树合并一个，因此摊销成本为 O(1)。因此，假设没有插入的删除，任何一系列 n 次插入到空二项式堆中，都将花费时间 O(n)。与二进制堆不同，即使您事先不知道元素 n 的数量，这也有效。
或者，您可以使用惰性二项式堆，其中插入需要最坏情况的时间 O(1)，而删除需要分期 O(log n)。在这种情况下，一系列 n 次插入也将花费 O(n) 时间。
希望这可以帮助！
于 2014-06-10T21:59:14.443 回答