求最大2堆中的kth最大元

Question

这个问题来自于一次采访：

在两个最大堆的联合中找到kth最大元素，假设这个kth元素出现在O(k log n)的两个堆中。

这是我想出的算法：

While k is not zero
 if(root of max-heap #1 > root of max-heap #2)
 {
    extract-max(heap #1)
 }
 else if(root of max-heap #1 < root of max-heap #2)
 {
    extract-max(heap #2)
 }
 else //case of duplicates
 {
    extract-max(heap #1)
    extract-max(heap #2)
 }
 k--

因此，当k=0时，提取-max函数将提取出最大的kth。

我认为该算法将在O(k log n)时间内运行，因为提取-max操作将在O(log n)中运行，并且我执行了k次。

这样做对吗？似乎我没有使用给定的信息“这个kth元素出现在两个堆中”？有没有更好的方法利用这些信息？

Answer 1

你的方法很好，不能改进太多。它也有预期的复杂性，所以你应该做得很好。我想到并可以优化的唯一一件事是，在最后一种情况下，只需检查k是否为零：

While true
 if(root of max-heap #1 > root of max-heap #2)
 {
    extract-max(heap #1)
 }
 else if(root of max-heap #1 < root of max-heap #2)
 {
    extract-max(heap #2)
 }
 else //case of duplicates
 {
    extract-max(heap #1)
    extract-max(heap #2)
    if (k == 1) {
      break;
    }
 }
 k--

通过这种方式，您可以减少平均情况下的比较次数(这将产生非常轻微的影响)。这还利用了提供给您的附加信息--元素对于两个堆都是通用的。但是，我不认为任何基准都不会注意到这种改进，因为extract远远超过了比较的复杂性。