algorithm - 如何将二叉堆转换为二项式队列

Question

给定一个二叉堆，如何在线性时间 O(n) 内将其转换为二项式队列？我想拆分堆但是我被卡住了，因为删除时间是 O(lg n)

Answer 1

假设您可以访问包含二叉堆的后备数组，并且可以在 O(n) 时间内对其进行迭代，那么您只需执行 n 次插入即可创建二叉堆。作为Wikipedia article说:

Inserting a new element to a heap can be done by simply creating a new heap containing only this element and then merging it with the original heap. Due to the merge, insert takes O(log n) time. However, across a series of n consecutive insertions, insert has an amortized time of O(1) (i.e. constant).

换句话说，对二项式堆进行 n 次插入将需要 O(n) 的时间。

使用标准二叉堆删除操作无法在 O(n) 时间内完成此操作。如您所述，每次删除的复杂度为 O(log n)，导致复杂度为 O(n log n)。