Clever Geek Handbook

Max Heapify-pseudocode

I am confused about one part of this pseudocode for Max Heap Sort. What does up 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)
+3


source to share


2 answers


This means that you are repeating this block for each value i in {length[A], length[A] - 1, length[A] - 2, ..., 2}

.

If it was C (or C ++ or Java - still the same syntax for that), it could be written:



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


source


Heapsort is essentially a sort of 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, the largest element in the array A [1..n] is selected and replaced with A [n]. Then select the largest element in the array A [1..n-1] and replace it with A [n-1]. Repeat this process until in the last iteration we find the largest element in [1..2] and replace it with A [2]. At this moment the elements of A [2..n] are in the correct position, and therefore A [1] is also in the correct position and the array is sorted.

It's almost like a sorting sort (where we'll pick the largest element from A [1..i] and replace it with A [i]), except that in heapsort A [1..i] is stored using a data structure called maxheap, so that the process of selecting the largest element is not performed using a linear search (for example, in sorting), but by modifying the array as much as possible and thereby brings the largest element to the first position of A [1]. Therefore, finding the largest element takes logarithmic time, not linear time.



The above algorithm can be formulated as follows: for i = n, n-1, ..., 2 (in this order) find the largest element from A [1..i] and change it to A [i]. Since i takes values ​​in this descending order, the for loop can be written as: for i = n to 2.

0


source






More articles:


All Articles