Heap Sort from Intro to Algorithms in C++ Implementation using Vectors

Question

I have been working on Heap Sort Functions in C++ that follows the logic from our class book, Intro to Algorithms 3rd edition and am not getting the desired output. Have been working through this in my head and am close, but I am not seeing my error. I am using vectors and have omitted the code that reads the values from a separate text file.

Any ideas on where I am going wrong with the indexes in each version? Adding, the input list I am using to test is 10 15 8 3 16 20 11 12 5 7 4 1 19 13 2 6 9 14 17 18.

The first method I tried is closer to the book but was giving output of 10 19 20 15 17 16 11 12 13 9 18 14 8 7 6 4 3 2 5 1. This is my preferred solution if I could figure out how I am messing up the indexing.

void maxHeapify(vector&);
void buildMaxHeap(vector&);
void heapSort(vector&);

int main(int argc, char * argv[])
{
if (argc <= 1)
{
    std::cerr << "A file was not found or is not accessable." << std::endl;
    return (1);
}

vector list;
int loc;

ifstream fin(argv[1]);

while (fin >> loc)
{
    list.push_back(loc);
}

// print unsorted list
cout << "Unsorted List:
";
for (int i = 0; i < list.size(); ++i)
    cout << list[i] << ' ';
cout << endl;

heapSort(list);

// print sorted list
cout << "Sorted List:
";
for (int i = 0; i < list.size(); ++i) {
    cout << list[i] << " ";
}
cout << endl;

cin.get();

return(0);
}

/* Heap Sort from Textbook using Vectors ***********************************/
void maxHeapify(vector& A, int i)
{
int largest;
int l = 2 * i;
int r = (2 * i) + 1;

if ((l <= A.size()) && (A[l] > A[i]))
    largest = l;
else
    largest = i;

if ((r <= int(A.size())) && (A[r] > A[largest]))
    largest = r;

if (largest != i)
{
    swap(A[i], A[largest]);
    maxHeapify(A, largest);
}
}

void buildMaxHeap(vector& A)
{
for (int i = int((A.size()-1) / 2); i >= 1; i--)  
{
    maxHeapify(A, i);
}
}

void heapSort(vector& A)
{

buildMaxHeap(A);
for (int i = int(A.size()-1); i >= 2; i--)  
    swap(A[1], A[i]);
    maxHeapify(A, 1);
}
}

The second method I tried ends up with an output 2 1 3 4 5 6 7 8 9 11 12 13 14 15 16 17 18 19 20 to 50 on a randomly sorted list of 50 integers but is correct on a list of only 20 random integers. The code is as follows:

void maxHeapify(vector&, int, int);
void buildMaxHeap(vector&, int);
void heapSort(vector&, int);

int main(int argc, char * argv[])
{
if (argc <= 1)
{
    std::cerr << "A file was not found or is not accessable." << std::endl;
    return (1);
}

vector list;
int loc;

ifstream fin(argv[1]);

while (fin >> loc)
{
    list.push_back(loc);
}

// print unsorted list
cout << "Unsorted List:
";
for (int i = 0; i < list.size(); ++i)
    cout << list[i] << ' ';
cout << endl;

clock_t begin = clock();

heapSort(list, int(list.size() - 1));

clock_t end = clock();
double elapsed_secs = double(end - begin) / CLOCKS_PER_SEC;  //only reports in seconds, need to replace.  

printf("Heap Sort Elasped time is %0.6f seconds.", elapsed_secs);
cout << endl;

// print sorted list
cout << "Sorted List:
";
for (int i = 0; i < list.size(); ++i) {
    cout << list[i] << " ";
}
cout << endl;

cin.get();

return(0);
}

/* Heap Sort from Textbook using Vectors ***********************************/
void maxHeapify(vector& A, int i, int n)
{
int largest;
int l = 2 * i;
int r = (2 * i) + 1;

if ((l <= n) && (A[l - 1] > A[i - 1]))
    largest = l;
else
    largest = i;

if ((r <= n) && (A[r - 1] > A[largest - 1]))
    largest = r;

if (largest != i)
{
    swap(A[i - 1], A[largest - 1]);
    maxHeapify(A, largest, n);
}
}

void buildMaxHeap(vector& A, int n)
{
for (int i = n / 2; i >= 1; i--)
{
    maxHeapify(A, i, n);
}
}

void heapSort(vector& A, int n)
{

buildMaxHeap(A, n);
for (int i = n; i >= 2; i--)
{
    swap(A[0], A[i]);
    maxHeapify(A, 1, i - 1);
}
}

Sumeet · Accepted Answer

The algorithm provided in the book considers the indices as 1,2,3....N, they start from 1.

So just follow the algorithm but keep one thing in mind when we access array we must subtract 1 from the index

So your first method code should be:

void maxHeapify(vector& A, int i, int n)
{
int largest;
int l = 2 * i;
int r = (2 * i) + 1;

if ((l <= n) && (A[l-1] > A[i-1]))
    largest = l;
else
    largest = i;

if ((r <= n) && (A[r-1] > A[largest-1]))
    largest = r;

if (largest != i)
{
    swap(A[i-1], A[largest-1]);
    maxHeapify(A, largest, n);
}
}

In second method, what you are doing wrong is that you are checking bounds with respect to 0 based index.

We cannot go by 0 based index here, because for 0 index, the left child is at index 1, but 2*0 is 0 only, So the only way is to use 1 based index everywhere and only while accessing elements you subtract - 1

Heap Sort from Intro to Algorithms in C++ Implementation using Vectors

Answers (2)

Related Questions