Heap, how to insert?

[ggoubb]

The purpose of the Insert function is to add a new integer in the Heap assuming that it is not already full. If Heap capacity has been reached, it attempts to double the current capacity. If capacity cannot be doubled, it throws FullHeap.

Here is the Heap.h file
const int MAXSIZE = 4; // Default maximum heap size
class Heap // Smart Heap ADT as an array
{
private:
int* ptr; // Pointer to smart heap array
int maxsize; // Current maximum heap size
int num; // Current number of elements in heap
void Swap(int& a, int& b); // Swaps integers a and b

public:
Heap(); // Creates empty smart heap of MAXSIZE

~Heap();

void ReheapDown(int root, int bottom); // Repairs heap order property from root to leaf


void ReheapUp(int root, int bottom); // Repairs heap order property from leaf to root


bool IsFull();

bool IsEmpty();

void Insert(int n); // Inserts n into heap, doubling heap capacity if needed.


int DeleteMax(); // Deletes and returns max value from heap if heap not empty


void MakeEmpty(); // Makes heap empty

void Print(); // Write heaparray to stdout

int Size(); // Returns current number of element in heap

int Capacity(); // Returns current heap capacity
};

I'm not quite sure how to double the heap capacity.
Here is what I have for the Insert function.
void Heap::Insert(int n)
{
if (num==maxsize)
{
maxsize=maxsize*2;
int* newptr;
int i=0;
newptr=new int[maxsize];
while(i<num)
{
newptr[i]=ptr[i];
i++;
}
num++;
ptr[num-1]=n;
ReheapUp(0,num-1);
}
else
{
num++;
ptr[num-1] = n;
ReheapUp(0,num-1);
}
}

I got a segmentation fault here.

[r035198x]

An easy way to learn is to use cout statements in your code to find what the values of your variables are against what you are expecting them to be.

[vmpstr]

    while(i<num)
    {
    newptr[i]=ptr[i];
    i++;
    }
    num++;
    ptr[num-1]=n;
    ReheapUp(0,num-1);
    }
 

you want to add the following lines before num++

delete [] ptr;
ptr = newptr;
 

The reason you are getting a segfault is that you are trying to add an element to your old ptr, which is still of old size. newptr is of doubled size, but you are not using it yet. If you add the lines, the doubled space, address of which is stored in newptr, gets assigned to ptr.

[weaknessforcats]

How come your heap is an array?

I would have expected you would have a node containing the allocation information and that node would be in a heap data structure.

[ggoubb]

Thanks so much vmpstr!
It works!!