如何将二叉堆转换为二项式队列
How to convert a binary heap to binomial queue
给定一个二叉堆，如何在线性时间 O(n) 内将其转换为二项式队列？我想拆分堆但是我被卡住了，因为删除时间是 O(lg n)
假设您可以访问包含二叉堆的后备数组，并且可以在 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) 复杂性。
给定一个二叉堆，如何在线性时间 O(n) 内将其转换为二项式队列？我想拆分堆但是我被卡住了，因为删除时间是 O(lg n)
假设您可以访问包含二叉堆的后备数组，并且可以在 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) 复杂性。