Narue's Heap sort a further explanation?

[Micko]

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

[Narue]

I'll give you a hint. Think in terms of the heap invariant rather than a strict "swap with the largest child" algorithm, which the second solution given does less efficiently (even though it's easier to visualize).

[Micko]

I'll give you a hint. Think in terms of the heap invariant rather than a strict "swap with the largest child" algorithm, which the second solution given does less efficiently (even though it's easier to visualize).

Unfortunately I've already spent a lot of time thinking about your implementation, and I can say I know that it works, but what I don't understand is why there are testing with 2*k when 2*k is not a child of elmenet at index k. I'm interested to know why are you using that implementation when you're talking about children at 2*k+1 and 2*k+2?

[Narue]

>I'm interested to know why are you using that implementation when you're talking about children at 2*k+1 and 2*k+2?
The initial discussion is about the concept that's easiest to follow initially. A working traditional implementation is then given, followed by a simplification of the concept and implementation that's easier to wrap your head around (for me at least). The traditional implementation doesn't follow the concept exactly in favor of a more efficient algorithm that simply ensures a valid heap.

>I can say I know that it works
Of course it works. :) But do you understand how and why it works? That's the point of my hint, stop trying to fit the concept exactly (this implementation is different) and remember that heapsort always works provided you start with a valid heap.

You'll enjoy that "Ah ha!" moment, when it all starts to make sense. :)

[Micko]

Well, that "swap with the largest child" would be straightforward implementation and clearer to one who first trying to understand and implement algorithm.
I was thinking more about this:

void do_heap ( int a[], int first, int last ) 
{ 
    while (2 * first + 1 <= last) 
     { 
	int j = 2 * first + 1; 
	while (j < last && a [j] < a[j + 1]) 
		j++; 
        if (a[first] >= a[j]) break; 
	swap (&a[first], &a[j]); 
	first = j; 
     } 
} 
void heap_sort ( int a[], int first, int end )
{
	int i;
	for (i = end/2; i >=0 ;i--)
		do_heap(a, i, end);

	for (i = end ; i > 0; i--)
	{
		swap (&a[i], &a[first]);
		do_heap(a, 0, i-1);
	}
}

I think this implementation is closer to algorithm explanation and whole story about 2*k+1 and 2*k+2. Your implementation is very similar, but you use 2*k and 2*k+1 (j and j+1) and at first I thought about that zero based and one based array issue. I understand (generally) how your code works, but I'm not sure it fits algorithm explanation with left and right child... :-|

[Micko]

I'm surprised that no one else commented this.
What do you think about this implementation Narue?

[Narue]

>What do you think about this implementation Narue?
Looks okay to me.

>I'm surprised that no one else commented this.
I'm almost finished with my red black tree tutorial. I'll make some adjustments and clarifications on the sorting tutorial after I post that one.

[Micko]

Can you tell me, when new edition of sorting tutorial is expected Narue?
Can anybode suggest any good book on algorithms in C, but not too hard for beginers?

[Narue]

>Can you tell me, when new edition of sorting tutorial is expected Narue?
Sometime in November, I would wager.

>Can anybode suggest any good book on algorithms in C, but not too hard for beginers?
Algorithms in C by Robert Sedgewick is great on theory and explanation. The code is godawful, but can be useful if you know not to copy it. ;) There really aren't any algorithm books that cater to beginners without being useless, so just look for something with "algorithms" or "data structures" in the name and grab it if you find it easier to understand. Rest assured that you will be getting several books on the subject. I probably have a dozen. ;)