这个算法有什么问题吗？

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并将所有值弹出到一个新的数组中。