Hello,

I'm trying to understand how this heap sort algorithm works

(how this particular implementation from www.eternallyconfuzzled.com) works.

```
void jsw_do_heap ( int a[], int begin, int end )
{
int save = a[begin];
while ( begin <= end / 2 ) {
int k = 2 * begin;
while ( k < end && a[k] < a[k + 1] )
++k;
if ( save >= a[k] )
break;
a[begin] = a[k];
begin = k;
}
a[begin] = save;
}
void jsw_heapsort ( int a[], int begin, int end )
{
int i,j;
for ( i = ( end - 1 ) / 2; i >= begin; i-- )
{
jsw_do_heap ( a, i, end - 1 );
printf("\n");/* showing array after do_heap*/
for ( j = begin; j < end; ++j)
{
printf("%d ",a[j]);
}
}
for ( i = end - 1; i > begin; i-- ) {
jsw_swap ( &a[i], &a[begin] );
jsw_do_heap ( a, begin, i - 1 );
}
}
```

Well, for zero-based array if parent is at index i then its childred are

at 2*i+1 and 2*i+2. By reading this code, I know that jsw_do_heap function is most important. I tested this code and it magicaly works but here's what

I'm having problem to understand:

```
int k = 2 * begin;
while ( k < end && a[k] < a[k + 1] )
++k;
```

If this code is tested with the following array:

ar[]= 4 8 2 1 5 2 4

with first call of do_heap

```
for ( i = ( end - 1 ) / 2; i >= begin; i-- )
{
jsw_do_heap ( a, i, end - 1 );
```

subarray 1 5 2 4 is passed to do_heap function and aftter that function call

whole array look like this: 4 8 2 4 5 2 1.

So now, I can see that 1 on index 3 is swapped with 4 on index 6. Here's what I don't understand. Index was 3 so left child would be at 2*i+1 = 7 and right child would be 2*i+2 = 8 (of course there are no elements there).

Sa basically element at index 3 is swapped with element at index 6. (i with 2*i) so I simply don't understand how is that story and algorithm with checking parent and both left and right child (i, 2*i+1 and 2*i+2) implemented with this heap sort? I think that algorithm description and implementation are very different or maybe not?

I think simple steps would be:

1. parent is at index i

2. left child is at 2*i+1 (if such index exists in an array)

3. right child is at 2*i+2 (if such index is allowed in an array)

4. find max (left child, right child)

5. swap founded max with parent

Can you at least comment this Narue's code or something I really don't understand how story about left child and riht child is implemented using

```
int k = 2 * begin;
while ( k < end && a[k] < a[k + 1] )
++k;
```

Thanks