heapsort algorithm clarifications when sorting is actually done

Question

I have some question about heapsort and about the heap involved in that.

1. when you build the meax-heap from an array, actually you build that heap a standalone object, or you just arrange the array to allow following the algorithm to build the heap to construct from that a max-heap?

2. after you rearrange the array in the order that represents a a max-heap you want sort that array or produce another array sorted from the elements of that array.

The algorithm to do that is:

A -- is an array example: {5, 3, 17, 10, 19,84, 6, 22, 9}

HEAPSORT(A)

1 BUILD-MAX-HEAP(A) 
// here you rearrange the array to represent a max heap or
 you actually construct a maxheap from that?

//a max heap array representation will be:
 {84, 22, 17, 10, 19, 5, 6, 3, 9}

 2 for i = A.length downto 2{
 3   exchange A[1] with A[i];
 4   A.heap-size = A.heap-size - 1; -- what this do in fact?
 5  MAX-HEAPIFY(A, 1);
}

From my point of view it seems to actually create a heap of array A size (a max-heap actually). Then on what is done actually the iteration, aparently is over the array and MAX-HEAPIFY - now on a shrieked heap somehow .

Can you clarify me with those things step by step?

Answer 1

After, some time spent on searching I found why there is a heap-size, and also an array.length (the array is actually the object where the heap is represented). If you don't want actually to have more free spots at the array tail and when you add an element in the heap you you will increase the array size with only 1 spot, then you don't actually need the heap-size, because they will be always identical, and that is array.length.

However if you do that, that will be a naive implementation of the heap over the array, because every time when you add, or delete/extract an element to/from the heap/array the cost of that operation will be O(n) because you will be forced to copy the values of the old array into the new array.

But when we remove/extract a node, we are not shrinking in fact the array, the operation of removing will cost us in a max/min heap O(log n), why?

when we remove item/node - actually the root - from the heap we just do the following: (to simplify thing we will use int)

1 store the root in auxiliary variable: int returnObj = array[0]; cost O(1)
2 put the value from the last element of the heap(why not array because only the heap-size 
will decrease, the array length is the same) into the first 
heap/array element array[0]=array[heap-size-1]; heap-size at the beginning == array.length
2.1 right now we have have last element ==first element, 
and we need to shrink the heap represented on the array somehow. 
Now comes the reason to have a heap-size variable independent of array.length if we don't 
want to actually shrink the array because that operation will cost us O(n-1) time 
- instead of doing that we will use an auxiliary variable heap-size, 
as i mentioned above-to mark the end of the heap, to be able to ignore tail elements of the 
array that actually are not part of the heap any-more.
2.2 because right now the first element of the array and also is the first element of 
the heap is actually one of the smallest - i am saying is one of the smallest because 
it is not mandatory that the last element to be the smallest to satisfy  the heap property, 
example {84, 22, 17, 10, 19, 5, 6, 3, 9} is a max-heap - 
we need to call max-hipify over array[0] ... to ... array[heap-size] to recreate the max-heap 
again. That will cost us O(log n) in the worst case, much less than O(n).

3 return returnObj;