Logical Error in Heapsort C++

[revots]

I was trying to make a program to dynamically size an array, take an input to that array, and then sort the array. I have not implemented any user error checking. Anyways, Everything seems to work except that the Heap sort fails to sort correctly. I have scanned over the code repeatedly but fail to find the source. It is a logical error, but I am not sure where.

Also this is not homework, this is just side hobby work.

order of calls
smallest -> HeapSort -> BuildHeap -> Left -> Right

ex.
input 5 numbers ( 5 4 3 2 1)
output ( 3 1 2 4 5)

	int Left(int i)
	{
		return (2*i);
	}
	
	int Right(int i)
	{
		return (2*i +1);
	}

		void Heapify(int A[],int i, int heapsize)
	{
		int l = Left(i),
		r = Right(i),
		largest, temp;
		if ( l <= heapsize && A[l] > A[i]){
			largest = l;
		}
		else {
			largest = i;
		}
		if (r <= heapsize && A[r] > A[largest]){
			largest =r;
		}
		if (largest != i)
		{
			temp = A[l];
			A[l] = A[largest];
			A[largest] = temp;
			Heapify(A,largest, heapsize);
		}
	}

	void BuildHeap(int A[],int heapsize)
	{
		for (int i = (heapsize -1)/2; i>=0; i--)
		{
			Heapify(A,i,heapsize);
		}

	}
	
	
	void HeapSort(int A[],int heapsize) //this part was based off of anothers code
	{
		int temp;
		BuildHeap(A, heapsize);
				cout << "\nFirst Call \n";
		for(int j = 0; j<heapsize; j++)
		{
			cout << A[j] << " ";
		}
		for (int i = heapsize; i>0; i--)
		{
			temp = A[0];
			A[0] = A[heapsize -1];
			A[heapsize -1] = temp;
			heapsize = heapsize - 1;
			Heapify(A,0, heapsize);

		}
	}

	int Smallest()		// find smallest of several ints
	{
		cout << " Prog to sort and tell you smallest int entered \n\n";

		int* arrayPtr;   // Pointer to int, initialize to nothing.
		int n;					// Size needed for array
		
		//Setup
		cout << "Enter the number of digits you will enter \n";
		cin >> n;				// Read in the size
		arrayPtr = new (nothrow) int[n];  // Allocate n ints and save ptr in a.

		cout << "\nEnter your digits eg. 1 2 3 4 5 \n";
		for(int i = 0; i < n; i++)
		{
			cin >> arrayPtr[i];
		}
		cout << "\nyou entered \n";
		for(int j = 0; j<n; j++)
		{
			cout << arrayPtr[j] << " ";
		}

		//sorting
		HeapSort(arrayPtr,n);

		//something to print
		cout << "\nHopefully Sorted \n";
		for(int j = 0; j<n; j++)
		{
			cout << arrayPtr[j] << " ";
		}

		return(0);
	}

Any Help is much appreciated.

[soranz]

Hi, just wondering if u can add a couple more examples to illustrate how u want things sorted and/or explain it more clearly...Thanks

[KRAkatau]

Hi,

you have several problems in your code - see my comments

#include <iostream>
using namespace std;

int Left(int i)
{
    return (2*i + 1); // The neighbors were computed incorrectly - imagine i = 0
}

int Right(int i)
{
    return (2*i +2); // Same here
}

void Heapify(int A[],int i, int heapsize)
{
    int l = Left(i),
        r = Right(i),
        largest, temp;
    if ( l < heapsize && A[l] > A[i]){     // you shouldn's make an inclusive check: '<' instead of '<='
        largest = l;
    }
    else {
        largest = i;
    }
    if (r < heapsize && A[r] > A[largest]){  // same here
        largest =r;
    }
    if (largest != i)
    {
        temp = A[i];      // you were swapping with the left child node, not the parent node - this is incorrect
        A[i] = A[largest];
        A[largest] = temp;
        Heapify(A,largest, heapsize);
    }
}

void BuildHeap(int A[],int heapsize)
{
    for (int i = (heapsize -1)/2; i>=0; i--)
    {
        Heapify(A,i,heapsize);
    }

}


void HeapSort(int A[],int heapsize)
{
    int temp;
    BuildHeap(A, heapsize);
    cout << "\nFirst Call \n";
    for(int j = 0; j<heapsize; j++)
    {
        cout << A[j] << " ";
    }
    for (int i = heapsize; i>0; i--)
    {
        temp = A[0];
        A[0] = A[heapsize -1];
        A[heapsize -1] = temp;
        heapsize = heapsize - 1;
        Heapify(A,0, heapsize);

    }
}

Also, if you need to find the smallest element - sorting the array is not the fastest way (although writing a heapsort function is certainly a good exercise) - scanning through the array would do it in O(n) instead of O(n log(n))

[revots]

Sorry if I am unclear. I have never asked questions in a forum before. The intent of the heapsort is to sort smallest to largest so reading array[0] once sorted will produce the smallest int. The heapsort method for this purpose is inefficient, I just wanted practice implementing some sorting algorithms.

Thanks to both of you for input. It is appreciated. I will try the suggestions listed.

A side note, does anyone have a good explanation for understanding the concept that heapsort in a diagrammatic sense is taking a one dimensional line and forcing the sort into a two dimensional sense. I seem to have a hard time keeping this conceptually. I think it is that I do not understand these binary trees yet.
eg
heaping A[n] looks like

                       A[0]
                        w
         /                           \
      A[1]		              A[2]
       y		                x
   /       \		             /     \
A[4]	     A[5]	         A[6]    etc.

/Edit/
To avoid double posting, your comments solved the issue. The neighbors were not necessarily incorrect, in that so far using mine our yours seems to sort properly. Further testing might show that under some circumstance they are wrong. For safety sake I am going to trust you answer. Thank you very much.