我正在阅读 CLRS，练习 6.5-8 遇到了一些问题。
给出一个 O（n lg k）-time 算法将 k 个排序列表合并为一个 排序列表，其中 n 是所有输入中的元素总数 列表。（提示：使用 min0heap 进行 k 方式合并。
正如大家所说，解决方案是，
1） 使用 k 列表的第一个元素构建一个 k 元素最小堆，
2） extract-min（） 从堆中获取最小的元素并将其附加到结果列表中，
3）从与我们刚刚从堆中提取的元素相同的列表中选择下一个元素。将其插入堆中并转到 2）。
我可以理解时间为 O（n lg k），但我没有得到步骤 3 中选择的正确性）。这似乎很明显，但有一些正式的证据吗？
正确性证明的主要内容是，剩余的元素最少的元素始终是要提取的元素。支持这一说法的关键不变性是，对于每个列表，优先级队列包含该列表中剩余的最少元素。从这个不变量中可以得出，由于剩余的最小元素也是其列表中剩余的最小元素，因此它由 extract-min 返回。
我们需要从第 3 部分中的同一列表中选择一个元素，以保持每个列表在队列中具有最少元素的不变性。否则，我们可能会遇到这样的情况
1 2
3 4
如果我们从包含 1 和 3 的初始队列中提取 1 并将其替换为 4，则下一个提取将是 3，这是错误的。