algorithm - 无法理解 K-way 合并算法(给出了反例)

Question

在K路归并排序中，使用堆的解决方案:本质上是维护一个堆，并不断从该堆中提取最大值。我有一个反例来说明为什么这行不通。

5 -> 1 -> 0
4 -> 2 -> 1
3 -> 2 -> 0

假设我们初始化我们的堆。它包含 {5, 4, 3}。

我们运行 extract max，我们得到 5 并将其添加到我们的新列表(代表最终解决方案)。我们的堆现在看起来像 {4,3}。然后我们用我们从中提取最大元素的列表的头部重新填充我们的堆。

这意味着我们得到这样的结果:{4, 3, 1}。

这对我来说没有意义。这个堆不再代表前 K 个元素。 1 不应该用来重新填充堆，它应该是 2。所以，这个 O(nlgk) 方法对我来说没有多大意义。

我希望有人能阐明这个算法是如何工作的，因为我被困在这里了。

Answer 1

最大堆总是包含 k 个列表(或数组)的最大元素。对于您的“反击”示例:

5 -> 1 -> 0
4 -> 2 -> 1
3 -> 2 -> 0

堆是 {5, 4, 3} 包含这三个列表的最大元素。

现在你从堆中提取 5，意味着你也从第一个列表中删除 5:

5-->1-->0: after extract 5, the list now is 1-->0: so 1 now is the top of the list.

那么新堆是{4, 3, 1}，仍然包含列表的最大元素。

让我们继续你的例子:提取 5 和堆化后的当前堆是:

{4, 3, 1}

从堆中提取 4，意味着您还从中删除了 4:

4-->2-->1: remove 4 you have 2-->1. 2 now is the top element of the list.

那么现在有一个新堆

{3, 2, 1}

继续这样做，你会得到你想要的(降序列表)。