从两个加权集合中按照每个对的求和权重的顺序有效地计算对

Question

假设我有两组数据，每个条目由一个权重组成。每一套都是按重量升序排列的。我将列出几个示例集：

Set 0: {4, 8, 19, 25, 25, 26}    
Set 1: {1, 2, 3, 8, 20, 27}

Answer 1

让我们表示两个排序列表A（大小m）和B（大小n）。

算法：

1. 计算所有i=0到n-1的a[0]和b[i]之和。您需要从列表A中确定和包括了哪个元素--一种方法是附加索引（这里所有和都是0）。将所有对推入按和排序的最小堆。
2. 弹出堆，取出总和。使用所附的索引与列表A中的下一个元素计算和。如果索引已经是m-1，则不需要做任何事情；否则，增加索引并将其推回到堆中。
3. 重复步骤2，直到堆为空（对于所有m*n值）。

通过使用上面算法中较小的列表作为列表B，我们可以实现稍微好一点的时间复杂度（我们只需要管理一个小堆而不是一个大堆）。

使用std::priority_queue的实现（由堆栈器）：

#include <iostream>
#include <set>
#include <queue>
#include <limits>

std::multiset<int> set1 {4, 8, 19, 25, 25, 26};
std::multiset<int> set2 {1, 2, 3, 8, 20, 27};

struct Node
{
  Node(std::multiset<int>::const_iterator set1Iterator, int set2Value) :
    set1Iterator(set1Iterator),
    set2Value(set2Value),
    sum(*set1Iterator + set2Value)
  {
  }

  bool operator < (const Node& other) const
  {
    return sum > other.sum; // Reverse order as std::priority_queue sorts for the greatest value
  }

  std::multiset<int>::const_iterator set1Iterator;
  int set2Value;
  int sum;
};

int main()
{
  std::priority_queue<Node> heap;
  for (auto i = set2.begin(); i != set2.end(); ++i)
    heap.push(Node(set1.begin(), *i));

  while (!heap.empty())
  {
    Node min(heap.top());
    heap.pop();

    std::cout << *min.set1Iterator << " + " << min.set2Value << " = " <<
      min.sum << std::endl;
    if (++min.set1Iterator != set1.end())
    {
      min.sum = *min.set1Iterator + min.set2Value;
      heap.push(min);
    }
  }
  return 0;
}