algorithm - 具有相同密钥算法的两个堆

Question

嗨，如果您有两个堆，您如何确定它们在 O(nlogn) 运行时中是否具有相同的键，其中 n 是两个最小堆之间的总大小。

我在想这可能与将其中一个堆添加到另一个堆有关，但我并不积极。

Answer 1

bool have_same_element(heap<int> h1, heap<int> h2) {
  while (!h1.empty() && !h2.empty()) {
    int t1 = h1.top(), t2 = h2.top();
    if (t1 == t2) return true;
    if (t1 < t2) h1.pop();
    else h2.pop();    
  }
  return false;
}

O(s1 ln(s1) + s2 ln(s2)) 保证 O(n ln(n)) 其中 n = s1+s2;

Answer 2

我认为堆结构无助于解决此类任务，因此无论您有两个堆还是两个项目数组都没有关系。要查找两个数据集是否具有相同的值，您可以使用不同的算法，我建议两个例如：

1. 您可以将较小集合的项目放入任何基于哈希的字典中，然后您可以枚举另一个集合的项目并检查它们是否在第一个集合中。可能这是最快的方法，但需要一些额外的字典空间。

2. 假设您有 2 个保存在数组中的经典堆结构（对于堆来说是可能的）。然后你可以对最小的数组进行排序。之后只需枚举第二个堆的项目并使用二进制搜索来检查项目是否在第一个堆中。完成后，您可以再次重建损坏的堆（可以在项目所在的同一数组中内联）。所以你得到 O(nlogn) 其中 n 是较小堆的数量，并且可以在没有额外内存使用的情况下完成。