Insert a Value into an Array-Based Heap

[TheFearful]

I keep getting a corruption for my array and I do not know why. Can anyone help me figure out what is causing my run-time error to happen?
my heapInsert function is at the very bottom

#include <iostream>
#include <algorithm>

using namespace std;

//function prototypes
int getParent(int index);
int getLeftChild(int index);
int getRightChild(int index);
void swap(int& item1, int& item2);
void heapify(int A[], int index, int size);
void build_heap(int A[], int size);
void printArray(int A[], int size);
void heapInsert(int A[], int &size, int Item);


int main()
{

    int A[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
    int size = sizeof A/sizeof(int);

    cout << "Print Array A: " << endl;
    printArray(A, size);
    cout << endl;

    cout << "Parent of node 5" << " is the node " << getParent(5) << endl;
    cout << "Left child of the node 3" << " is the node " << getLeftChild(3) << endl;
    cout << "Right child of the node 3" << " is the node " << getRightChild(3) << endl;
    cout << "Print Heap A:" << endl;
    build_heap(A, size);
    printArray(A, size);
    heapInsert(A, size, 20);
    cout << "\nAfter inserting the number into the heap A:" << endl;
    build_heap(A, size);
    printArray(A, size);
    return 0;
}

void printArray(int A[], int size)
{
    if(size == 0)
    {
        return;
    }
    else
    {
        printArray(A, size -1);
        cout << A[size - 1] << " ";     
    }
}

int getParent(int index)
{
    return(index/2);
}

int getLeftChild(int index)
{
    return(index * 2 + 1);
}

int getRightChild(int index)
{
    return(index * 2 + 2);
}

void swap(int &item1, int &item2)
{
    int temp = item1;
    item1 = item2;
    item2 = temp;
}

void heapify(int A[], int index, int size)
{
    int left = getLeftChild(index);
    int right = getRightChild(index);
    int largest;
    if(left < size && A[left] > A[index])
    {
        largest = left;
    }
    else
    {
        largest = index;
    }

    if(right < size && A[right] > A[largest])
    {
        largest = right;
    }

    if(largest != index)
    {
        swap(A[index], A[largest]);
        heapify(A, largest, size);
    }
}

void build_heap(int A[], int size)
{
    for(int i = size/2; i >= 0; i--)
    {
        heapify(A, i, size);
    }
}

void heapInsert(int A[], int &size, int Item)
{

    size = size + 1;
    int i = (size - 1);


    while(i > 0 && A[getParent(i)] < Item)
    {
        cout << A[i] << endl;
        A[i] = A[getParent(i)]; 
        i = getParent(i);
        A[i] = Item;
    }
    cout << A[i];
    //i = getParent(i);
    //A[i] = Item;

}

[Ancient Dragon]

Probably because heapInsert() changes the value of size from 10 to 11 and there aren't 11 elements in the array. You can't just arbitrarily change the size of a statically declared array.

[TheFearful]

But I inserted the value 20 into the array so that there would be 11 element? Or do I have to dynamically allocate an array to make this possible?

[Ancient Dragon]

Yes, the array has to be dynamically allocated, then in heapInsert() you have to increase the size of the array to accommodate the new element. That becomes much easier and faster if you used a standard tree of allocated nodes instead of putting everything in one big chunck of memory.

[TheFearful]

I don't get a run-time error, but I still don't have the output I need. I don't think I can try to dynamically allocate it in my main since my heapInsert is void.

void heapInsert(int A[], int &size, int Item)
{

    size = size + 1;
    int i = size - 1;
    int *B = new int[size];

    while(i > 0 && A[getParent(i)] < Item)
    {
        B[i] = A[getParent(i)]; 
        i = getParent(i/2 - 1);
        cout << B[i] << endl;
        //i = getParent(i);
    }
    A[i] = Item;
}

[Ancient Dragon]

array B in that function has no value because it doesn't change the size of array A.

In main(), change array A to be a pointer and initially allocate it to contain 10 elements. Then in heapInsert increase the size of A by 1. You will have to change the signature of heapInsert() a little because you have to pass a pointer to a pointer so that heapInert() can change the address of the pointer in main().

void heapInsert(int **A, int &size, int Item)

[TheFearful]

But wouldn't I then have to change all of my other functions as well because of the change to A?

[Ancient Dragon]

Yes, some of the other functions will also have to change, especially those called from main()

void heapInsert(int **A, int &size, int Item)
{

    size = size + 1;
    int i = size - 1;
    int *B = new int[size];
    memcpy(B, *A, (size-1)*sizeof(int)); // copy old array to new
    delete[] *A;
    *A = B;

    while(i > 0 && *A[getParent(i)] < Item)
    {
        *A[i] = *A[getParent(i)]; 
        i = getParent(i/2 - 1);
        cout << *A[i] << endl;
        //i = getParent(i);
    }
    *A[i] = Item;
}

[Ancient Dragon]

After thinking about it, this might be a bit easier to work with

void heapInsert(int **A, int &size, int Item)
{

    size = size + 1;
    int i = size - 1;
    int *B = new int[size];
    memcpy(B, *A, (size - 1)*sizeof(int)); // copy old array to new

    while (i > 0 && B[getParent(i)] < Item)
    {
        B[i] = B[getParent(i)];
        i = getParent(i / 2 - 1);
        cout << B[i] << endl;
        //i = getParent(i);
    }
    B[i] = Item;
    delete[] * A;
    *A = B;
}

[TheFearful]

I am getting a compile error because I can't convert from 'int *' to 'int **[]

[Ancient Dragon]

repost the probram and tell me what line the error is on. If this error is in main() than most likely it's because you have to pass a pointer to A, for example if A is a pointer then

heapInsert(&A, ... )

[TheFearful]

    int *A[10];
    *A[0] = 4;
    *A[1] = 1;
    *A[2] = 3;
    *A[3] = 2;
    *A[4] = 16;
    *A[5] = 9;
    *A[6] = 10;
    *A[7] = 14;
    *A[8] = 8;
    *A[9] = 7;
    int size = 10;

    cout << "Print Array A: " << endl;
    printArray(*A, size);
    cout << endl;

    cout << "Parent of node 5" << " is the node " << getParent(5) << endl;
    cout << "Left child of the node 3" << " is the node " << getLeftChild(3) << endl;
    cout << "Right child of the node 3" << " is the node " << getRightChild(3) << endl;
    cout << "Print Heap A:" << endl;
    build_heap(*A, size);
    printArray(*A, size);
    heapInsert(&A, size, 20); //This is where I get the error


    cout << "\nAfter inserting the number into the heap A:" << endl;
    build_heap(*A, size);
    printArray(*A, size);
    return 0;
}

void printArray(int A[], int size)
{
    if(size == 0)
    {
        return;
    }
    else
    {
        printArray(A, size -1);
        cout << A[size - 1] << " ";     
    }
}

int getParent(int index)
{
    return(index/2);
}

int getLeftChild(int index)
{
    return(index * 2 + 1);
}

int getRightChild(int index)
{
    return(index * 2 + 2);
}

void swap(int &item1, int &item2)
{
    int temp = item1;
    item1 = item2;
    item2 = temp;
}

void heapify(int A[], int index, int size)
{
    int left = getLeftChild(index);
    int right = getRightChild(index);
    int largest;
    if(left < size && A[left] > A[index])
    {
        largest = left;
    }
    else
    {
        largest = index;
    }

    if(right < size && A[right] > A[largest])
    {
        largest = right;
    }

    if(largest != index)
    {
        swap(A[index], A[largest]);
        heapify(A, largest, size);
    }
}

void build_heap(int A[], int size)
{
    for(int i = size/2; i >= 0; i--)
    {
        heapify(A, i, size);
    }
}

void heapInsert(int **A[], int &size, int Item)
{
    size = size + 1;
    int i = size - 1;
    int *B = new int[size];
    memcpy(B, *A, (size - 1)*sizeof(int)); // copy old array to new
    while (i > 0 && B[getParent(i)] < Item)
    {
        B[i] = B[getParent(i)];
        i = getParent(i / 2 - 1);
        cout << B[i] << endl;
        //i = getParent(i);
    }
    B[i] = Item;
    delete[] * A;
    *A = B; //I also get an error here
}

[Ancient Dragon]

lines 1-10 are incorrect -- all line 1 does is declare an array of pointers, not an array of integers

int *A = new int[10];
    A[0] = 4;
    A[1] = 1;
    A[2] = 3;
    A[3] = 2;
    A[4] = 16;
    A[5] = 9;
    A[6] = 10;
    A[7] = 14;
    A[8] = 8;

line 15: should be printArray(A, size);

[Ancient Dragon]

line 102 is wrong

void heapInsert(int **A, int &size, int Item)

[TheFearful]

That certainly fixed my compile error! Thank you! Now, I need to figure out why it is not printing out the heap properly when I do the insert.