algorithm - 这个算法有问题吗？

Question

我对堆排序算法有疑问

Heap_Sort(A)
  Build_Heap(A)
  for i<--n down to 2
    swap (A[1],A[n])
    n<--n-1
    MaxHeapify(A,1)

我认为我们应该写而不是这个算法：

Heap_Sort(A)
  Build_Heap(A)
  for i<-- n down to 1
    Delete_Max(A)

Answer 1

如果你正在做一个就地排序......

Heap_Sort(A)
    B = Build_Heap(A)    # Assuming maxheap

    for i -> A.length to 0:
        Remove top value from B (which is basically just A, but treated differently),
        assuming the heap is modified to maintain partial ordering during this part
        (as well as decreasing the noted size of the heap by 1) and add the removed
        value to position A[i].

基本上你的算法。但是，如果您没有进行适当的排序，您可以简单地使用 minheap 并将所有值弹出到一个新数组中。

Answer 2

如果您将最大元素移动到堆数组的后面然后删除它，那么完成后您将不会在数组中留下任何东西。因此，删除最大值的算法不会产生原始元素的排序数组。

基于 OP 编辑​​的更新：

你可以这样做。但是，第一种方法允许您就地排序。您的方法需要 O(N) 额外的存储空间。

另一个编辑：

很难准确看出您对第一个算法做出了什么假设，但当我想到我在下面所做的评论时，似乎MaxHeapify(A,1)应该是MaxHeapify(A, n). 您通常会传递一个数组及其大小，或者在这种情况下，您要作为堆排列的元素数量。如果您假设 n 是全局变量，这可能没有实际意义。