Build Max Heap algorithm won't work

Question

I am trying to build a max heap using the algorithm given in Introduction to Algorithms, and I can't get it to work. Firstly, I'm having some interesting issues with passing arrays between functions. My understanding is that arrays are passed by reference in C++, but after I pass an array and I check the addresses of the argument and the parameter they don't match. When I try to use sizeof() on an array that is a parameter it doesn't return the correct value.

Secondly, the algorithm just doesn't seem to work. It does make some changes to the array, and gets the numbers closer to a heap but still has a ways to go. I've checked the code dozens of times and it seems to be spot on with pseudo code given in my text. What am I missing?

#include <iostream>
#include <ctime>

#define N 10
#define DISPLAY

using namespace std;


// Display an array
void display(double p[]) {
#ifdef DISPLAY
    for (int i = 0; i < N; i++) cout << p[i] << " ";
    cout << endl;
#endif
}


inline int parent(int i)
{return i/2;}

inline int left(int i)
{return 2*i;}

inline int right(int i)
{return 2*i+1;}

void maxHeapify(double p[], int i)
{
    int largest;

   int l = left(i);
   int r = right(i);

   if (l <= N && (p[l] > p[i]))
        largest = l;

    else
        largest = i;

    if (r <= N && (p[r] > p[largest]))
        largest = r;

    if (largest != i)
    {
        double temp = p[i];

        p[i] = p[largest];

        p[largest] = temp;

        maxHeapify(p, largest);
    }
}   

void buildMaxHeap(double p[])
{
    for (int i=N/2; i>0; i--)
        maxHeapify(p, i);
}

int main() {
 double a[] = {4,1,3,2,16,9,10,14,8,7};
 buildMaxHeap(a);
 display(a);
}

I take it std::make_heap() is off the reservation for things you can use? (in case not reinventing the wheel is an option for you). — WhozCraig

colin chen colin chen · Accepted Answer · 2013-02-23T22:12:44

I modified your code as below:

#include <iostream>
#include <ctime>

#define N 10
#define DISPLAY

using namespace std;


// Display an array
void display(double p[]) {
#ifdef DISPLAY
    for (int i = 0; i < N; i++) cout << p[i] << " ";
    cout << endl;
#endif
}


inline int parent(int i)
{return i/2;}

inline int left(int i)
{return 2*i;}

inline int right(int i)
{return 2*i+1;}

void maxHeapify(double p[], int i)
{
    int largest;

   int l = left(i)-1;
   int r = right(i)-1;
   i=i-1;

   if (l <= N && (p[l] > p[i]))
        largest = l;

    else
        largest = i;

    if (r <= N && (p[r] > p[largest]))
        largest = r;

    if (largest != i)
    {
        double temp = p[i];

        p[i] = p[largest];

        p[largest] = temp;

        maxHeapify(p, largest+1);
    }
}   

void buildMaxHeap(double p[])
{
    for (int i=N/2; i>0; i--)
        maxHeapify(p, i);
}

int main() {
 double a[] = {4,1,3,2,16,9,10,14,8,7};
 buildMaxHeap(a);
 display(a);
}

Build Max Heap algorithm won't work

1 Answers