Implementing a Heap

So I'm going through and trying to do a recursive implementation of a Heap. I keep getting access violations for some reason on my sifts (_siftUp) - even though I'm trying to insert into sub[0] (currSize = 0 in the constructor). I don't think either of my sifts are implemented correctly, are they?

Here's my Heap:

Code:

---

#ifndef HEAP_H
#define HEAP_H
//**************************************************************************
template<typename TYPE>
class Heap
{
        private:
                TYPE* heapData;
                int currSize;
                int capacity;
                void _siftUp(int);
                void _siftDown(int);
                int _leftChildOf(int) const;
                int _parentOf(int) const;

        public:
                Heap(int c = 100);
                ~Heap();
                bool viewMax(TYPE&) const;
                int getCapacity() const;
                int getCurrSize() const;
                bool insert(const TYPE&);
                bool remove(TYPE&);
};
//**************************************************************************
template<typename TYPE>
Heap<TYPE>::Heap(int c = 100)
{
        capacity = 100;
        currSize = 0;
}
//**************************************************************************
template<typename TYPE>
Heap<TYPE>::~Heap()
{
        delete heapData;
        currSize = 0;
        capacity = 0;
}
//**************************************************************************
template<typename TYPE>
bool Heap<TYPE>::insert(const TYPE& dataIn)
{
        bool success = false;
        if(currSize < capacity)
        {
                heapData[currSize] = dataIn;
                _siftUp(currSize);
                currSize++;
                success = true;
        }
        return success;
}
//**************************************************************************
template<typename TYPE>
void Heap<TYPE>::_siftUp(int child)
{
        TYPE temp;
        int parent;
        if(child > 0)
        {
                parent = _parentOf(child);
                if(heapData[child] > heapData[parent])
                {
                        temp = heapData[parent];
                        heapData[parent] = heapData[child];
                        heapData[child] = temp;
                        _siftUp(child);
                }
        }
}
//**************************************************************************
template<typename TYPE>
bool Heap<TYPE>::remove(TYPE& dataOut)
{
        bool success = false;
        if(currSize > 0)
        {
                dataOut = heapData[0];
                currSize--;
                heapData[0] = heapData[currSize];
                _siftDown(0);
                success =  true;
        }
        return success;
}
//**************************************************************************
template<typename TYPE>
void Heap<TYPE>::_siftDown(int parent)
{
        TYPE temp;
        int child = _leftChildOf(parent);
        if(child < currSize)
        {
                if((child + 1 < currSize) && (heapData[child] < heapData[child + 1]))
                        child++;

                if(child)
                {
                        temp = heapData[child];
            heapData[child] = heapData[child + 1];
            heapData[child + 1] = temp;
            _siftDown(child);
                }
        }
}
//**************************************************************************
template<typename TYPE>
int Heap<TYPE>::_leftChildOf(int p) const
{
        return(2 * p + 1);
}
//**************************************************************************
template<typename TYPE>
int Heap<TYPE>::_parentOf(int c) const
{
        return((c - 1) / 2);
}
//**************************************************************************
template<typename TYPE>
int Heap<TYPE>::getCapacity() const
{
        return capacity;
}
//**************************************************************************
template<typename TYPE>
int Heap<TYPE>::getCurrSize() const
{
        return currSize;
}
//**************************************************************************
template<typename TYPE>
bool Heap<TYPE>::viewMax(TYPE& max) const
{
        return false
}
#endif

---

Please modify your post to put the missing final ] after the [/code at the end so that the code tags work. Also it would be useful to format your code before posting for indents etc.

What debugging of the code have your done to try to identify the problem?

I've debugged it in VS but it breaks when I assign

Code:

---

heapData[currSize] = dataIn;

---

in my insert. I haven't got to my remove yet but I imagine i'll run into the same problems. I set currSize to 0 in my constructor and I run into this problem when I try to insert the first or 1 item.

The error messages tells me that I have an access violation.

heapData is a pointer, but I don't see where you point it to valid memory.

In the destructor ~Heap you have

Code:

---

Heap<TYPE>::~Heap()
{
        delete heapData;
        currSize = 0;
        capacity = 0;
}

---

which deletes the heapData memory.

However in the constructor Heap you have

Code:

---

Heap<TYPE>::Heap(int c = 100)
{
        capacity = 100;
        currSize = 0;
}

---

You don't use c and you don't allocate memory for heapData using new.

Oh right, I need to initialize my array with capacity, whoops >.>