algorithm - 以最有效的方式将几个预先排序的列表合并到一个联合列表中（并获取其中的顶部元素）

Question

我有这样一个预设：

• 许多预先排序的有序列表，例如，1000 个元素，每个元素都按标准排序（例如，基于时间的“最后一个”）
• 需要制作一个保持排序顺序并且还包含 1000 个最后元素的联合列表（因此可以丢弃不适合前 1000 个的原始列表的元素）。但是，也可以单独选择 1000 个顶部。
• 合并需要尽可能快、尽可能高效。重新排序完整的合并列表不是一种选择。

标签： algorithmlistlinked-list

Answer 1

使用任何基于优先级队列的数据结构：

priority queue q = empty
for each list add first element to q
create an array next that contains next elements for every list (initially next element is a second element)

while result list is not full
    take top element from the q and add to the result list
    add next element of the corresponding list to the q (if any)
    update next element of the corresponding list