arrays - 有效合并多集的 n 个元素的数据结构

Question

我正在尝试解决以下问题。让我们定义 2 个多重集操作:

1. |M,e|有序多重集的操作最低 e多重集的元素 M .例如，|{1,1,2,3,3,4},4|={1,1,2,3} .
2. 替代总和集 [E,F,G,e]作为:
   • [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

肯定有类似堆的数据结构可以更快地进行合并，例如 Fibonacci heap或 pairing heap .但是，任何类似堆的数据结构在查找 m 最小条目时都会变慢；这几乎总是 O(m log(n))。如果 m 的值通常很小，则值得尝试，但如果 m 通常不会比 n 小很多，我猜您当前的解决方案总体上可能更快。