heap sort problem

I'm trying to sort an array of numbers with heap sort, but it's not sorting the first number in the array.
Here is my code:

Code:

#include <iostream>
using namespace std;

int BuildMaxHeap(int array1[], int n);
int MaxHeapify(int array1[], int i, int n);
int Heapsort(int array1[], int n);

int main()
{
	int array1[11] = {11, 2, 4, 6, 8, 0, 1, 3, 5, 7, 9};

	Heapsort(array1, 10);

	for (int z = 0; z < 11 ; z++)
	{
		cout << array1[z] << " ";
	}
	cout << endl;

	return 0;
}
int MaxHeapify(int array1[], int i, int n)
{
	int c=0;
	int l = i << 1;					++c;
	int r = (i << 1) + 1;			++c;
	int largest;						++c;

	// Is left larger than i?
	if (++c && (l <= n) && (array1[l] > array1[i]))
	{
		largest = l;					++c;
	}
	else
	{
		largest = i;					++c;
	}

	// Is right larger than largest?
	if (++c && (r <= n) && (array1[r] > array1[largest]))
	{
		largest = r;					++c;
	}

	// Need swap??
	if (++c && largest != i)
	{
		int temp = array1[i];				++c;
		array1[i] = array1[largest];				++c;
		array1[largest] = temp;				++c;
		c += MaxHeapify(array1, largest, n);	++c;
	}

	return c;
}
int BuildMaxHeap(int array1[], int n)
{
	int c=0;
	for (int i = n / 2; ++c && i >= 1; i--)
	{
		c += MaxHeapify(array1, i, n);	++c;
	}

	return c;
}
int Heapsort(int array1[], int n)
{
	int c=0;
	BuildMaxHeap(array1, n);				++c;
	for (int i = n; ++c && i >= 2; i--)
	{
		// exchange i with 1
		int temp = array1[1];			++c;
		array1[1] = array1[i];				++c;
		array1[i] = temp;				++c;

		c += MaxHeapify(array1, 1, i-1);	++c;
	}
	return c;
}

I'm pretty sure the reason is because the whole sorting algorithm is made for a 1 based array (where the first position is 1, not 0). I'm pretty sure it's an easy fix, but i've been trying for a long time and can't figure it out. If I made the first position in the array a dead spot, and shifted the values one spot, this would fix the problem, but i can't figure out how.
Also, for my real program, i read the numbers in from a file ( i created the above one so it could be copied and pasted to run. The real program requires a file, and needs to be run using the command prompt, so the solution to my problem could be slightly different in each case):

Code:

int main(int argc, char* argv[])
{

	int *array1 = NULL;
	int size;
	
	//First value in the file is assigned to "size".
	inFile >> size;	
	
	array1 = new int[size];

	//FillArray
	for (int i = 0; i < size; i++)
	{
		inFile >> array1[i];
	}

	//InsertionSort(array1, size);
	//Quicksort (array1, 0, size-1);
	Heapsort(array1, size-1);
	//MergeSort(array1, 0, size-1);
	//BubbleSort(array1, size);
	//ShellSort(array1, size);
	PrintArray(array1, size);	

	delete [] array1;
	array1 = NULL;
	cin.get();
	return 0;
}

In this, i launch the program in the command prompt like:

Code:

program file.txt

and the file looks like (the first number is the number of values, and the rest are just random values):

Code:

10
1
6
4
8
2
4
9
8
4
2

All my other sorting algorithms work in this program except for the heap sort. Once again, i think it's because of the 0 based array problem.

Thanks.

The main change you need to make to make heapsort work with a zero-based array is to change the child indexing from this:

Code:

	int l = i << 1;
	int r = (i << 1) + 1;

to this:

Code:

	int r = (i + 1) << 1;
	int l = r - 1;

Otherwise you can't pass i=zero because i<<1 is still zero. With this change, the children of index zero become 1 and 2 - just what you want.
You then have to change this line:

Code:

	c += MaxHeapify(array1, 1, i-1);

to this:

Code:

	c += MaxHeapify(array1, 0, i-1);

and also adjust the start and end values of your decrementing for loops but one. There might be more you need to change, but you can probably figure the rest out on your own.

Oh I see you have used recursion in MaxHeapify! You definitely shouldn't do that. Yes it will work, but one noted advantage of heapsort is that it is one of the algorithms that doesn't require anything more than constant space, and your implementation uses log(n) stack space.

I also strongly suggest you make the function interfaces consistent. You should never have to pass in 'size' to some algorithms and 'size-1' to others. This parameter should always be the number of items to sort. If you have to, subtract 1 inside the start of the sorting function.

Since you seem to be interested in a number of sorting algorithms, you may want to have a look at my webpage, which contains the implementations of at least 60 array sorting algorithms, all in C++.

That fixed it.
Thanks.