algorithm - 使用多个堆的 Heapsort

Question

我在 http://students.ceid.upatras.gr/~lebenteas/Heapsort-using-Multiple-Heaps-final.pdf 找到了使用多个堆的 Heapsort 变体.该解决方案建议代替传统的 Heapsort 算法，在每次交换之后，我们再做一次 siftdown 以将当前堆中的最高值带到根，我们可以这样做其他一些事情。然而，他们所说的“其他事物”到底是什么意思，我无法理解。

例如，有一次他们说我们暂时“忘记”了根的存在。这肯定意味着我们目前正在停止最高元素与最后一个元素的交换堆的元素。然而，就在几行之后，他们说到目前为止，两个元素已经转移到堆的已排序部分。，这与交换尚未完成的命题背道而驰。同样在第97页的图中，值为1的节点丢失了，我不知道如何。

谁能告诉我作者到底想表达什么，它有多大值(value)？

Answer 1

(你问的那行在2.3节，所以我会解释2.3节提出的heapsort的变体:)

当作者说我们“忘记”了根的存在时，这并不意味着他们正在拖延最高元素的交换。交换已经完成，但他们暂时延迟了堆的重建。将最高元素交换到根位置后，他们比较 2 个子堆的根，并用次高元素交换一个或另一个。 然后，在进行 2 次交换(而不是 1 次)后，他们重建堆。

然后他们在第 3 部分和第 4 部分将这个想法更进一步，并提出另一种堆排序变体，它使用多个堆。

如何在数组中保留多个堆？ (为了具体起见，让我们谈谈 2 个堆。)那么，如何保留一个堆？根位于索引 0，其子堆位于 1 和 2，然后左侧子堆的子堆位于 3 和 4，依此类推，对吧？

要将 2 个堆放在一个数组中，请将 2 个根保持在 0 和 1。第一个根的 child 在 2 和 3，然后第二个根的 child 在 4 和 5 ...安排，仍然可以通过对索引进行简单的算术运算来在树上上下导航。

标准堆排序重复 2 个步骤:将根元素与“堆”区域中的最后一个元素交换，然后siftDown 重建堆。 这个 heapsort 重复以下 3 个步骤:比较 2 个根以查看哪个更大，将那个与“堆”区域中的最后一个元素交换，然后调用 siftDown在适当的堆上。

这需要在每一步进行额外的比较，但是 siftDown 操作适用于稍微浅一点的堆，这比一次比较节省更多。