algorithm - 有效计算 n 个集合的交集

Question

我有n由 标识的集合setId，每个集合都可以包含任意数量的一对元素(elementId, priority)。

我的算法应该接受输入二setId，并在输出中给出一个包含第一个m元素的集合，这些元素位于两个输入集合的交集中并且具有最高优先级（优先级总和）。

例子：

n=3, m=1

Set1: { (1, 1), (12, 2) }
Set2: { (1, 4), (23, 6), (33, 22) }
Set3: { (33, 1), (1, 16 }


Input: Set2, Set3
Output: { (33, 23) }

我的问题是：假设我有无限的空间，我可以使用什么来优化性能的最佳数据结构？

当然，预先计算所有可能的交集不是一个有效的答案。

编辑：

现实数字：

• n, 集数, 是~ 10^6
• 集合的平均基数是~ 5*10^3.

Answer 1

取其中一组并将其转换为哈希映射。迭代另一个集合，并为每个成员尝试在哈希映射中查找元素。如果找到它，将结果添加到堆中；如果堆的大小增长到比您希望保留的元素数量大一，请丢弃堆中最低的项目。