数据结构以有效地合并多个集合的n个元素

Question

我正在努力解决以下问题。让我们定义两个多集操作：

1. 对于有序多集的|M,e|操作，作为多集M的最低e元素。例如，|{1,1,2,3,3,4},4|={1,1,2,3}。
2. 可选和集[E,F,G,e] as：
   • [E,F,G,e]=|E+F,e|，如果多重集E的所有元素之和都是偶数，
   • [E,F,G,e]=|E+G,e|，如果多重集E的所有元素之和都是奇数

​

例如：[{0,2},{1,2},{0,3},3]=|{0,2}+{1,2},3|=|{0,2,1,2},3|=|{0,1,2,2},3|={0,1,2}

问题是:给出一个n非空自然数多集族：X={x(0), x(1), …, x(n-1)}和数字m与k，求出多集之和是下列运算的结果：[…[[{},x(i_0),x(j_0),m],x(i_1),x(j_1),m]…,x(i_(k-1)),x(j_(k-1)),m]，即在起始集({})上应用k乘以可选和运算，给出<i,j>对。

现在，我已经使用多集的数组表示和合并两个多集的效率来解决这个问题，因为我可以合并两个有序数组，同时裁剪它的大小(在O(l)中，l是被合并的两个数组的大小的min() )，并同时对结果数组进行求和。

但我认为可能有一种更快的基于树/堆的解决方案，可以让我更快地合并多集，并以更灵活的方式保存有关多集和的信息。

在这种情况下，什么样的数据结构是最好的选择？

Answer 1

当然，有些类似堆的数据结构可以更快地完成合并，例如斐波纳契堆或配对堆。但是，任何类似堆的数据结构在查找最小的条目时都要慢一些；这几乎总是O(m log(n))。如果m的值通常较小，则值得一试，但如果m通常不小于n，我猜您当前的解决方案可能更快。