Heap sort, a little help

[Micko]

Hello, by searching explanations and code for heap sort I found tghis code:

#include <stdio.h>

#define less(a, b) ((a) < (b))

static void exchange ( int *a, int *b )
{
  int t = *a;
  *a = *b;
  *b = t;
}

static void fixDown ( int *a, int k, int N )
{
  int j;
  while ( 2 * k <= N ) {
    j = 2 * k;
    if ( j < N && less ( a[j], a[j+1] ) )
      j++;
    if ( !less ( a[k], a[j] ) )
      break;
    exchange ( &a[k], &a[j] );
    k = j;
  }

 /* Look at here*/
  for (j = 0; j<10; j++)
	  printf ("%d ",a[j]);/* first element is -858993460*/
  printf("\n");
}

static void heapsort ( int *a, int l, int r )
{
  int k, N = r - l + 1;
  int *pq = a + l - 1;
  for ( k = N / 2; k >= 1; k-- )
    fixDown ( pq, k, N );
  while ( N > 1 ) {
    exchange ( &pq[1], &pq[N] );
    fixDown ( pq, 1, --N );
  }
}

int main ( void )
{
  int i;
  int a[10] = {8,3,9,1,0,5,9,3,6,4};
  heapsort ( a, 0, 9 );
  printf("\n");
  for ( i = 0; i < 10; i++ )
    printf ( "%d ", a[i] );
  printf ( "\n" );
  return 0;
}

I think Narue wrote it on another forum. I wanted to see how fix down works and I decided to print array elements each time fixdown function is called. but when I use for loop like in the code a[0] is some garbage value, but when I put j = 1 and loop end condition to j <=10, everthing seems OK, but, if I'm not wrong that means that array boundary is passed and that is potential run time error.
Can anyone comment this and explain if this code passing beyond array bounds or not?

Thanks

[Narue]

>I think Narue wrote it on another forum.
I sure hope not. You're looking at a common bug/assumption with the heapsort algorithm. A lot of the time, people writing about heapsort will assume that arrays are 1 based instead of 0 based, which results in an off-by-one error when an unsuspecting programmer translates into C. A surprisingly many "professional-grade" implementations fall into either this trap or another trap of "fixing" the problem in a naive way.

If it really was my code, I'll blame it on copy/paste and not paying attention when I was in a hurry. ;) I'll direct you here before you're led too far astray by my laziness. ;)

[Micko]

Thanks for the reply, I'll read your tutorial throughly when I have time. I saved that code a long time ago and I think it is from cboard, but never mind that.
Thanks again

P.S. In one of mine earlier implementation I used something like this:

For creating heap

template <class T>
void Sort<T>::kreiraj_heap(T array[],int first,int last)
{
	int i=first,flag_swap=1;
	while(flag_swap)
	{
		flag_swap=0;
		T tmp;
		while(2*i+2<=last)
		{	
			tmp=max(array,2*i+1,2*i+2);
			if(array[i]<array[tmp])
			{
				
				swap(array[i],array[tmp]);
				flag_swap++;
			}
			i++;
		}
		
		if(2*i+1<=last)
		{
			
			if(array[i]<array[2*i+1])
			{
				swap(array[i],array[2*i+1]);
				flag_swap++;
				i++;
			}
		}
		i=first;		
	}
}

And heap sort function:

template <class T>
void Sort<T>::heap_sort(T list[])
{
	
	for(int i=length-1;i>0;i--)
	{
		kreiraj_heap(array,0,i);
		swap(array[0],array[i]);
	}

}

I used logic that if i is parent the, children are 2*i+1 and 2*i+2.
Can you comment this. Comparing with your code I think it's fairly inefficient...

- Micko