algorithm - Heapsort 的这种优化有多值得？

Question

传统的Heapsort 算法在每次heapification 后将堆的最后一个元素与当前堆的根交换，然后再次继续该过程。但是，我注意到这是不必要的。

在子数组的堆化之后，当节点包含最高值(如果它是max-heap)时，数组中接下来的 2 个元素 < em>必须 跟在已排序数组的根之后，要么按照与现在相同的顺序，要么在反向排序时交换它们。因此，与其将根与最后一个元素交换，不如将前 3 个元素(包括节点以及在必要时交换第二个和第三个元素之后)与最后 3 个元素交换，这样 2随后的heapifications(对于第二个和第三个元素)被免除了？

这种方法有什么缺点吗(除了如果需要交换第二个和第三个元素，这应该是微不足道的)？如果不是，如果确实更好，它会带来多少性能提升？这是伪代码:

function heapify(a,i) {
  #assumes node i has two nodes, both heaps. However node i itself might not be a heap, i.e one of its children may be greater than its value.
  #if so, find the greater of its two children, then swp the parent with that value.
  #this might render that child as no longer a heap, so recurse
 }

function create_heap(a) {
   #all elements following index |_n/2_| are leaf nodes, thus heapify() should be applied to all elements within index 1 to |_n/2_|
   }

function heapsort(a) {
  create_heap(a);  #a is now a max-heap
  #root of the heap, that is a[1] is the maximum, so swap it with a[n].
  #The root now contains an element smaller than its children, both of which are themselves heaps.
  #so apply heapify(a,1). Note: heap length is now n-1, as a[n] is the largest element already found
  #now again the array is a heap. The highest value is in a[1]. Swap it with a[n-1].
  #continue
  }

假设数组是[4,1,3,2,16,9,10,14,8,7]。运行一个heapify后，它将变成[16,14,10,8,7,9,3,2,4]。现在 heapsort 的第一次迭代将交换 16 和 4，导致 [4,14,10,8,7,9,3,2,16]。因为这现在已经将新堆的根 [4,14,10,8,7,9,3,2] 呈现为，嗯，未堆，(14 和 10 都更大比 4)，运行另一个 heapify 来生成 [14,8,10,4,7,9,3,2]。现在 14 是根，将它与 2 交换以产生 [2,8,10,4,7,9,3,14]，从而使数组当前为 [2,8, 10,4,7,9,3,14,16]。我们再次发现 2 未堆，因此再次执行 heapify 使堆成为 [10,8,9,4,7,2,3]。然后将 10 与 3 交换，使数组成为 [3,8,9,4,7,2,3,10,14,16]。我的观点是，我们可以从第一个 heapification 中看出，因为 10 和 14 在 16 之后，所以我们可以从第一个 heapification 中看出，它们是第二大和第三大元素(反之亦然)。因此，在比较它们之后(如果它们已经排序，14 在 10 之前)，我将所有 (16,14,10) 替换为 (3,2,4) ，生成数组 [3,2,4,8,7,9,16,14,10]。这将我们简化为与另外两个 heapification 之后的情况类似的情况 - [3,8,9,4,7,2,3,10,14,16] 最初，与现在的 [3,2,4,8,7,9,16,14,10] 相比。两者现在都需要进一步heapification，但是第二种方法让我们通过两个元素(14 和 10)之间的比较直接到达这个关头。

Answer 1

堆的第二大元素出现在第二或第三个位置，但第三大元素可以出现在更下方的深度 2 处。(参见 http://en.wikipedia.org/wiki/Heap_(data_structure) 中的图)。此外，将前三个元素与后三个元素交换后，heapify 方法将首先对根的第一个子树进行堆化，然后是根的第二个子树，然后是整棵树。因此，此操作的总成本接近于将顶部元素与最后一个元素交换并调用 heapify 的成本的三倍。所以这样做你不会有任何收获。