What is wrong with my insert function for min-heaps?

Question

I'm trying to write a minimum heap data structure in C, but I ran into some issues while implementing the insert function.

It looks like this :

void insert(MinHeap* minh , int key)
{
    if(minh->itemcount == minh->maxSize)
    { 
        printf("cant insert,heap is full\n");
        return;
    }
    minh->itemcount++;
    minh->HeapArray[minh->itemcount]=key;
    int parent=getParent(minh->itemcount);
    while(parent != 0 && minh->HeapArray[parent] > minh->HeapArray[minh->itemcount])
    {
        swap(&(minh->HeapArray[parent]), &(minh->HeapArray[minh->itemcount]));
        parent = parent/2;
    }
}

Now the insertion process works if I insert the following values:

insert(minheap,5);
insert(minheap,3);
insert(minheap,2);
insert(minheap,4);

The output came out to be:

2 4 3 5

This is a valid output, since it follows the minimum heap property.

But once I start adding more values like 1, the output is:

2 1 3 5 4

As can you see, there is "bubbling up" of 1 occurring, but it doesn't seem to go all the way up, since 1 should be the first element, not 2. I'm not sure why is this occurring, because my code for insertion has the same logic as any other minimum heap insertion function.

It would be great if anyone can help with clearing this up.

Some side notes:

MinHeap is a type-defined structure, and its members are :

typedef struct Heap
{
    int* HeapArray;
    int maxSize;
    int itemcount;
} MinHeap;

I have a created an "instance" (with malloc) of this structure in the main function. I also dynamically allocated memory for the HeapArray Member. I also set the itemcount member to be equal to 0.

Also, the indexing for my minimum heap array starts with 1 not 0, so the getParent function returns the following:

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

Answer 1

The main issue is that you are always swapping with the same element, i.e. with the last one at minh->HeapArray[minh->itemcount]: in the first iteration of the loop this is indeed the child of parent, but if there are more iterations, it no longer represents the child.

As a side issue: you have parent = parent / 2 in your loop: why didn't you use the getParent function here?

Secondly, the getParent function does not need to use floor: the division is already an integer division.

Here is the correction of where the main issue occurred:

    int child = ++minh->itemcount;
    minh->HeapArray[child] = key;
    int parent = getParent(child);
    while (parent != 0 && minh->HeapArray[parent] > minh->HeapArray[child]) {
        swap(&(minh->HeapArray[parent]) , &(minh->HeapArray[child]));
        child = parent;
        parent = getParent(child);
    }