我试图想出一个想法来做一个新的拆分操作，通过给定一个二项式堆。
问题是如何将二项式堆（大小 n）拆分为二项式堆大小 k （k
您可以使用中位数算法找到集合O(n) kth最大元素。源。
当您拥有该值时，您可以从原始堆中读取所有值（不需要提取，它们的顺序在读取时无关紧要，仅在写入新数组时无关紧要。这还有一个额外的好处，那就是不会弄乱原始堆。耶。并放入大堆或小堆中，具体取决于它们与kth值的关系。每次提取都是O(1)的，发生n次。每个插入O(lg n)，出现n次。
Total running time: n + n + n lg n = O(n lg n)
| | |
selection | inserts
extraction
您可以在 k*log（n） 中执行此操作，只需从原始堆中删除 k 个元素并将它们移动到新的不同堆中即可。（假设堆是最小堆，如果它是最大堆，则可以在（n-k）log（n）中以相同的方式完成）
因为二项式堆的树可以表示为 n 的二进制数字，所以您只需在 n 和 k 之间进行二进制长减法，就可以在 O（log（n）） 中拆分堆，每次您需要"借用"一个数字，您将分成一半树。 这就像二项式树合并，但使用二进制长减法而不是树上的加法。