algorithm - 证明使用最小堆合并 k 个排序列表的算法

Question

我正在阅读 CLRS，但在练习 6.5-8 时遇到了一些问题。

Give an O(n lg k)-time algorithm to merge k sorted lists into one sorted list, where n is the total number of elements in all the inputs lists. (Hint: use a min0heap for k-way merging.)

正如大家所说，解决方案是，

1) 使用 k 个列表的第一个元素构建一个 k 元素最小堆，

2) extract-min() 从堆中获取最小的元素并将其追加到结果列表中，

3) 从与我们刚刚从堆中提取的列表相同的列表中选择下一个元素。将其插入堆中并转到 2)。

我可以理解时间是 O(n lg k)，但我不明白第 3 步中选择的正确性。这似乎很明显，但是有一些正式的证据吗？

Answer 1

正确性证明的主旨是剩余最少的元素始终是要提取的元素。支持此声明的关键不变性是优先级队列包含，对于每个列表，该列表中剩余的最少元素。从这个不变量可以看出，由于剩余的最少元素也是列表中剩余的最少元素，它由 extract-min 返回。

我们需要从第 3 部分中的同一个列表中选择一个元素，以保持每个列表在队列中都有其最少元素的不变性。否则，我们可能会遇到这样的情况

1 2
3 4

如果我们从包含 1 和 3 的初始队列中提取 1 并将其替换为 4，则下一次提取将是 3，这是错误的。