is there any problem with this algorithm?

Question

I have a problem with this algorithm for Heap-Sort

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

I think instead of this algorithm we should write:

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

Answer 1

If you move the max element to the back of your heap array and then delete it, you're not going to be left with anything in your array when completes. So, your algorithm, which deletes the max, is not going to result in a sorted array of your original elements.

Update based on OP edit:

You can do it that way. The first method, though, allows you to sort in place. Your method requires O(N) additional storage.

Another Edit:

It's difficult to see exactly what assumptions you're making on the first algorithm, but as I think about the comment I made below, it seems likely that MaxHeapify(A,1) should probably be MaxHeapify(A, n). You will usually pass an array and its size, or in this case, the number of elements you want to arrange as a heap. This might be moot if you are assuming that n is a global variable.

Answer 2

If you're doing an in-place sort...

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].

Basically your algorithm. If you aren't doing the sort in place, though, you can simply use a minheap and pop all the values into a new array.