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

Question

(我得到了这个面试问题，希望得到一些帮助。)

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

中 k 个列表中的所有元素

Answer 1

想法是使用 min heap大小为 k。

将所有 k 列表推送到堆上(每个列表一个堆条目)，以它们的最小(即第一个)值作为键控

然后重复这样做:

1. 从堆中提取顶部列表(具有最小键)
2. 从该列表中提取最小值并将其压入结果列表
3. 将缩短的列表(如果它不为空)推回到堆上，现在以其新的最小值作为键

重复，直到所有值都被插入结果列表。

初始步骤的时间复杂度为 O(klogk)。

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

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

所以最终的复杂度是 O(nlogk)(因为 k <n，初始步骤并不重要)。