如何将排序的列表合并到O(n * log(k))中的单个列表中

Question

（我把这个作为面试问题，并希望提供一些帮助。）

您的k排序列表中包含n总数不同的数字。
显示如何创建一个单个排序列表，其中包含O(n * log(k))

Answer 1

这个想法是使用大小 k 。

的最小堆

按堆上的所有 k 列表（每个列表一个堆输入），由它们的最小值（即第一个）值

键入

然后反复这样做：

1. 从堆中提取顶部列表（具有最小键）
2. 从该列表中提取最小值并将其推在结果列表上
3. 将缩短列表向后推回（如果不是空），现在由其新的最小值
kemper

重复直到将所有值推到结果列表上。

初始步骤的时间复杂性为 o（klogk）。

上面的3个步骤将重复 n 次。在每次迭代中，每个迭代的成本是：

1. o（1）
2. o（1）如果使用指针/索引实现提取（不移动列表中的所有值）
3. o（log k），因为堆的大小永远不大于

因此，所产生的复杂性为 o（nlogk）（如 k ＆lt; em n ，初始步骤不重要）。

Answer 2

正如所述问题时，不需要K-way合并（或堆）。以任何顺序合并列表对，直到产生单个排序列表也将具有时间复杂性o（n log（k））。如果问题询问了如何在单个通过中合并k列表，则需要K-Way合并。

考虑k == 32的情况，为了简化数学，假设所有列表都按顺序合并，以便每个合并通过合并所有n个元素。在第一次通过之后，有k/2列表，在第二次通过之后，k/4列表之后，log2（k）= 5通过后，将所有k（32）列表合并为单个排序列表。除了简化数学，合并列表的顺序无关紧要，时间复杂性在O（n log2（k））时保持不变。

使用k-way合并通常仅在使用外部设备合并数据时，例如一个或多个磁盘驱动器（或经典用法磁带驱动器），其中i/o时间足够好，足够好，可以堆在开销上。被忽略。对于基于RAM的合并/合并排序，对于2条合并/合并排序或K-Way Merge/Merge排序，操作总数大致相同。在带有16个寄存器的处理器上，其中大多数用作索引或指针，优化（无堆）4向合并（使用8个寄存器作为索引或指针到每个运行的当前和结束位置）可能会更快一些）比由于更友好的高速缓存而不是2路合并。

Answer 3

当N=2时，您通过迭代弹出两个列表的列表合并，最小。在某种程度上，您创建了一个支持pop_front操作的虚拟列表，该列表为：

pop_front(a, b): return if front(a) <= front(b) then pop_front(a) else pop_front(b)

您可以很好地安排像树一样的合并方案，其中这些虚拟列表成对合并：

pop_front(a, b, c, d): return if front(a, b) <= front(c, d) then pop_front(a, b) else pop_front(c, d)

每个流行音乐都将涉及到树中的每个级别，从而导致每个pop的成本O(Log k)。

---

上述推理是错误的，因为它不考虑front操作，涉及两个元素之间的比较，这将级联级联，最后需要每个输出元素的k-1比较。

可以通过"记忆"前元素来规避这一点，即在进行比较后将其保留在两个列表旁边。然后，当弹出一个元素时，此前元素会更新。

正如@trincot所建议的。

    5 7 32 21
  5
    6 4 8 23 40
2
    7 7 20 53
  2
    2 4 6 8 10