我在http://students.ceid.upatras.gr/~lebenteas/Heapsort-using-Multiple-Heaps-final.pdfHeapsort找到了使用多个堆的变体。该解决方案提出，代替传统算法，在每次交换之后，我们再做一次以将当前堆中的最高值带到根，我们可以做一些其他的事情。但是，我无法理解他们所说的“其他事物”到底是什么意思。Heapsortsiftdown
例如，有一次他们说我们暂时“忘记”了根的存在。这肯定意味着我们目前正在暂停最高元素与堆的最后一个元素的交换。然而，就在几行之后，他们说到目前为止，已经在堆的排序部分转移了两个元素。，这与尚未完成交换的命题背道而驰。同样在第97页的图中，缺少值为1的节点，我不知道如何。
谁能给我一个关于作者试图传达的确切内容的想法，以及它有多大价值？
(The line you asked about is in section 2.3, so I will explain the variation of heapsort which is proposed in section 2.3:)
When the author says we "forget" the existence of the root, this does not mean that they are stalling the swapping of the highest element. The swap is done, but they temporarily delay rebuilding the heap. After swapping the highest element into the root position, they compare the roots of the 2 subheaps, and swap one or the other with the next-highest element. Then, after doing 2 swaps (rather than 1), they rebuild the heap.
Then they take this idea a step further in sections 3 and 4, and propose another variant of heapsort, which uses more than one heap.
How do you keep more than one heap in an array? (To make it concrete, let's talk about 2 heaps.) Well, how do you keep a single heap? The root goes at index 0, its children are at 1 and 2, then the children of the left subheap are at 3 and 4, etc., right?
To put 2 heaps together in an array, keep the 2 roots at 0 and 1. The children of the first root go at 2 and 3, then the children of the 2nd root at 4 and 5... with such an arrangement, it is still possible to navigate up and down the tree by doing simple arithmetic operations on indexes.
The standard heapsort repeats 2 steps: swap the root with the last element in the "heap" area, then siftDown to rebuild the heap. This heapsort repeats the following 3 steps: compare the 2 roots to see which one is bigger, swap that one with the last element in the "heap" area, then call siftDown on the appropriate heap.
This requires an extra compare at each step, but the siftDown operations work on slightly shallower heaps, which saves more than a single compare.