分裂二项式堆
我正在尝试想出一个想法来进行一个新的分割操作，通过给定一个 二项式堆 。
问题是如何将二项式堆（大小n）拆分为二项式堆 大小为 k (k < n) 的二项式堆，在最短运行时间内大小为 nk 的二项式堆。
I'm trying to think of an idea to make a new Split operation that By given a Binomial heap.
The question is how to split binomial heap (size n) into binomial heap
of size k (k < n), and binomial heap of size n-k within the minimal time of running.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
您可以使用中位数中位数算法在
O(n)时间内找到集合中的第 k 个最大元素。 来源。当您拥有该值时，您可以从原始堆中读取所有值（不需要提取，它们的顺序在读取时并不重要，仅在写入新数组时才重要。这还有一个额外的好处，即不会弄乱原始堆。）并放入大堆或小堆中，具体取决于它们与第 k 个值的关系。每次提取都是
O(1)并发生n次。每次插入都是O(lg n)并发生n次。You can find the
kthlargest element of a set inO(n)time with the median of medians algorithm. Source.When you have that value, you can read all values from the original heap (don't need to extract, their order doesn't matter on read, only on write in the new arrays. This has the added benefit of not messing with the original heap. Yay.) and put into the large or small heap, depending on their relation to the
kthvalue. Each extraction isO(1)and occursntimes. Each insert isO(lg n)and occursntimes.您可以在 k*log(n) 中执行此操作，只需从原始堆中删除 k 个元素并将它们移动到新的不同堆中即可。 （假设堆是最小堆，如果它是最大堆，则可以在 (nk)log(n) 中以相同的方式完成）
You can do this in k*log(n) by simply removing k elements from the original heap and moving them to a new different heap. (this assuming the heap is a minimum heap, if it's a maximum heap then it can be done the same way in (n-k)log(n))
因为二项式堆的树可以表示为 n 的二进制数字，所以您可以简单地通过在 n 和 k 之间进行二进制长减法来在 O(log(n)) 中分割堆，其中每次需要“借用”一个数字你把一棵树劈成两半的东西。它与二项式树合并完全相同，但在树上使用二元长减法而不是加法。
Because the binomial heap's trees can be represented as the binary digits of n, you can split the heap in O(log(n)) simply by doing a binary long subtraction between n and k where each time you need to "borrow" a digit what you split in half one tree. it's exactly like binomial trees merge but using a binary long subtraction instead of addition on the trees.