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;

}

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.

Edited 2 Years Ago by Ancient Dragon

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?

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.

Edited 2 Years Ago by Ancient Dragon

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;
}

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)

Edited 2 Years Ago by Ancient Dragon

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

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;
}

Edited 2 Years Ago by 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;
}

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

Edited 2 Years Ago by TheFearful

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, ... )

    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
}

Edited 2 Years Ago by TheFearful

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);

Edited 2 Years Ago by Ancient Dragon

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.

This question has already been answered. Start a new discussion instead.