Am I implementing the "Heapify" Algorithm correctly?

Question

I'm creating a heap implementation for a computer science class, and I was wondering if the following recursive function would create a heap out of an array object that was not already a heap. the code is as follows:

void Heap::Heapify(int i)
{
    int temp, l, r, heapify;
    l = LeftChild(i);// get the left child
    r = RightChild(i);// get the right child

    //if one of the children is bigger than the index
    if((Data[i] < Data[l]) || (Data[i]< Data[r]))
    {
        //if left is the bigger child
        if(Data[l] > Data[r])
        {
            //swap parent with left child
            temp = Data[i];
            Data[i] = Data[l];
            Data[l] = temp;
            heapify = l; // index that was swapped
        }
        //if right is the bigger child
        else
        {
            //swap parent with right child
            temp = Data[i];
            Data[i] = Data[r];
            Data[r] = temp;
            heapify = r; // index that was swapped
        }
        // do a recursive call with the index
        //that was swapped
        Heapify(heapify);
    }
}

the idea is that you see if the data at the index given is bigger than all of it's children. If it is, the function ends no problem. Otherwise, it check to see which is biggest(left or right children), and then swaps that with the index. The heapify is then called at the index where the swapping happened.

by ildjarn's request, I'm including my full class definition and implementation files to aid in the answering of my question:
here's the header file:

#ifndef HEAP_H
#define HEAP_H
//Programmer: Christopher De Bow
//Date: november 15, 2011

class Heap
{ 
private:
    int Data [100];
    int Parent(int);
    int RightChild(int);
    int LeftChild(int);
    void Heapify(int);
    void BuildHeap();

public:
    Heap();
    void insert();
    void HeapSort();
    void ExtractMaximum();
    int Maximum();
    void PrintHeap();
    int heapsize;
    void SetData(int[]);
};

#endif

and the implementation file:

#include <iostream>
#include "Heap.h"
using namespace std;
//Programmer: Christopher De Bow
//Date: november 15, 2011

Heap::Heap()
{
    int init [10] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    heapsize = 10;
    SetData(init);
}

int Heap::Parent(int index)
{
    int Rval;
    if(index%2 == 0)// if the index is even
    {
        Rval = ((index-1)/2);
    }
    else// if the index is odd
    {
        Rval = (index/2);
    }
    return Rval;
}

int Heap::RightChild(int arrplace)
{
    int ret;
    ret = ((2*arrplace)+2); //rightchild is index times 2 plus 2
    return ret;
}

int Heap::LeftChild(int i)
{
    int rval;
    rval = ((2*i)+1); //leftchild is index times 2 plus 1
    return rval;
}

void Heap::Heapify(int i)
{
    int temp, l, r, heapify;

    l = LeftChild(i); // get the left child
    r = RightChild(i); // get the right child

    if((l <= heapSize) && (data[l] > data[i]))
    {
        heapify = l;
    {
    else
    {
        heapfiy = i;
    }
    if((r <= heapSize) && (data[r] > data[heapify]))
    {
        heapify = r;
    }
    if(heapify != i) // one of the two child nodes has proved
    {                // larger than Data[i], so interchange values
        //swap parent with left child
        temp = Data[i];
        Data[i] = Data[heapify];
        Data[heapify] = temp;
        Heapify(heapify);
    }
}

void Heap::BuildHeap()
{
    // we do not have a heap
    // we will make a heap
    // by calling heapify starting at the lowest
    // internal node in the heap
    for(int i = heapsize; i >= 1; i--)
    {
        Heapify(i-1);
    }
}

void Heap::insert()
{
    int insert;
    heapsize = (heapsize + 1);
    //getting data from the user
    cout<<"what data would you like to insert?"<<endl;
    cin>>insert;
    Data[heapsize] = insert;
    BuildHeap(); //call BuildHeap on array
    cout<<"done"<<endl;
}

void Heap::PrintHeap()
{
    BuildHeap();
    for(int count = 0; count < (heapsize-1); count++)
    {
        cout<<Data[count];// print out every element in heap
    }
    cout<<endl<<endl;
}

void Heap::HeapSort()
{
    BuildHeap();
    int temp;
    // do this for every elem in heap:
    for(int i = 0; i < heapsize; i++)
    {
        temp = Data[heapsize-1];
        Data[heapsize-1] = Data[0];
        Data[0] = temp;
        heapsize--;
        BuildHeap();
    }
    PrintHeap();
}

void Heap::ExtractMaximum()
{
    BuildHeap();
    //assign last thing in heap to first thing in heap
    Data[0] = Data[heapsize];
    heapsize --; // decrease heapsize by one
    Heapify(0); // heapify from the top
}

int Heap::Maximum()
{
    int Rval;
    BuildHeap();// make sure we have a heap
    Rval = Data[0];
    return Rval; // return top thing
}

//initialize the elements in the "Data" array
void Heap::SetData(int x[])
{
    for(int i = 0; i <= (heapsize); i++)
    {
        Data[i] = x[i]; 
    }
}

Answer 1

Your algorithm works. The problem is in the translation of algorithm to code. Say you declared Data as :

int Data[7];

and you populate it with the initial values {0, 1, 2, 3, 4, 5, 6}. Presuming definitions of LeftChild(i) and RightChild(i) to be something like:

#define LeftChild(i) ((i << 1) + 1)
#define RightChild(i) ((i << 1) + 2)

then your function BuildHeap(), which should be something like:

void Heap::BuildHeap()
{
    for(int i = (7 >> 1); i >= 1; i--) // in general, replace 7 with 
                                       // (sizeof(Data)/sizeof(int)), presuming 
                                       // you have an array of int's. if not, 
                                       // replace int with the relevant data type
    Heapify(i-1);
}

will begin the Heapify process on the lower-right-most sub-tree root. In this case, this is array index 2, with a left child of 5 and a right child of 6. Heapify will correctly exchange 2 and 6 and recursively call Heapify(6).

Here the whole thing can run aground! At present your tree looks like :

                         0
                    1         2
                 3     4   5     6
            u n d e f i n e d  s p a c e

so the call Heapify(6) will dutifully compare the values of Data[6] with Data[13] and Data[14] (the perils of C++ and its lack of array boundaries enforcement, unlike Java). Obviously, the latter two values can be any junk left in RAM. One solution here, ugly but a working patch, is to add 8 elements in the declaration of Data and initialize them all to some value lower than any element of the array. The better solution is to add a heapSize variable to your class and set it equal to the length of your array:

heapSize = (sizeof(Data)/sizeof(int));

Then integrate logic to only compare child nodes if they are valid leaves of the tree. An efficient implementation of this is :

void Heap::Heapify(int i)
{
    int temp, l, r, heapify;

    l = LeftChild(i); // get the left child
    r = RightChild(i); // get the right child

    if((l <= heapSize) && (Data[l] > Data[i]))
        heapify = l;
    else heapfiy = i;
    if((r <= heapSize) && (Data[r] > Data[heapify]))
        heapify = r;
    if(heapify != i) // one of the two child nodes has proved 
                     // larger than Data[i], so interchange values
    {
        //swap parent with left child
        temp = Data[i];
        Data[i] = Data[heapify];
        Data[heapify] = temp;

        Heapify(heapify);
    }
}

So to summarize, the solution is as straightforward as adding logic to make sure the child nodes are valid leaves of the tree, and your main function will have something like :

Heap heap;

// initialize Data here    

heap.BuildHeap();

Hope that helps.

Answer 2

No. On the tree

      1
     / \
    /   \
   /     \
  2       3
 / \     / \
6   7   4   5

the output is going to be

      3
     / \
    /   \
   /     \
  2       5
 / \     / \
6   7   4   1

which has several heap violations. (I'm assuming that Data[l] and Data[r] are minus infinity if the corresponding children do not exist. You may need extra logic to ensure this.)

What your function does is fix a tree that may not be a heap but whose left and right subtrees are heaps. You need to call it on every node, in postorder (i.e., for i from n - 1 down to 0) so that the children of i are heaps when Heapify(i) is called.