斯普利特二项堆

我试图想到一个主意，使一个新的分支操作，通过给予Binomial heap。斯普利特二项堆

问题是如何在最小运行时间内将二叉堆（size n）拆分成大小为k（k < n）的二项式堆和大小为n-k的二项堆。

会是什么有这种拆分操作的好处（还有一个原因堆是分裂50/50）？你试过什么了？ – Davidann 2011-05-10 18:12:02

你可以找到O(n)时间中位数算法的中位数一组的kth最大的元素。 Source。

当你有一个值，你可以阅读从原来堆的所有值（不需要解压，它们的顺序读取上并不重要，只有在新的阵列写。这有额外的好处不要混淆原始堆，Yay），并将其放入大堆或小堆中，具体取决于它们与kth值之间的关系。每次提取是O(1)并发生n次。每个插入是O(lg n)并且发生n次。

Total running time: n + n + n lg n = O(n lg n) 
        | |  | 
      selection | inserts 
        extraction

2011-05-10 18:12:28 corsiKa

如果你已经执行O（nlogn）操作，为什么不从原始堆排序的所有值，发现第k个号码，插入所有入堆数比大，和所有小于该到另一个堆？似乎比使用中值算法更简单... – Gal 2011-05-11 08:17:28

@Gal因为没有必要。你的函数以最小的努力获得了30％的速度提升（算法已经为我们编写了，开发时间很短）。另外，你甚至不需要从原始数组中提取。你可以将它们全部阅读并插入。这又提高了30％。我刚刚意识到这一点。 – corsiKa 2011-05-11 08:20:08

您可以通过简单地从原来的堆取出k个元素，并将它们转移到一个新的不同的堆在K *的log（n）做到这一点。（这个假设堆是最小堆，如果它是一个最大堆那么它可以在（NK）的log（n）来完成同样的方式）

2011-05-11 08:21:26 Gal

回答