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