Max Heapify-pseudocode

Question

I'm confused on one part of this pseudocode for Max Heap Sort. What does down to 2 mean?

HeapSort(A)
Build-Max-Heap(A)
for i <-- length[A] down to 2
do exchange A[1] <---> A[i]
heap-size[A] =  heap-size[A] -1
Max-Heapify(A,1)

Answer 1

It means that you repeat that block for every value of i in {length[A], length[A] - 1, length[A] - 2, ..., 2}.

If this were C (or C++, or Java—all the same syntax for this), one could write it:

for (int i = length(A), i >= 2, i--) {
    do...
}

Answer 2

Heapsort is essentially selection sort, but with the unsorted part of the array stored in the form of a maxheap data structure. More specifically, heapsort works as follows. First selects the largest element in the array A[1..n], and swap it with A[n]. Then select the largest element in the array A[1..n-1] and swap it with A[n-1]. Repeat this process, until in the last iteration, we find the largest element in A[1..2] and swap it with A[2]. At this point the elements A[2..n] are in their correct positions, and so A[1] is also in its correct position and the array is sorted.

This is almost like selection sort (where we would select the largest element from A[1..i] and swap it with A[i]), except that in heapsort A[1..i] is stored using a data structure called a maxheap, so that the process of selecting the largest element is not done using linear search (like in selection sort) but by maxheapifying the array and thereby bringing the largest element to the first position A[1]. Hence, finding the largest element takes log n time rather than linear time.

The above algorithm can be phrased as: for i=n, n-1, ..., 2 (in that order), find the largest element in A[1..i] and swap it with A[i]. Since i takes values in that decreasing order, the for loop can be written as: for i = n downto 2.