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

Question

我正在阅读 CLRS 并且对练习 6.5-8 有一些问题。

给出一个 O(n lg k) 时间算法将 k 个排序列表合并为一个排序列表，其中 n 是所有输入列表中元素的总数。（提示：使用 min0heap 进行 k 路合并。）

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

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，这是错误的。