error while trying to create a minHeap from array

Question

I'm trying to get a minHeap from an array, but I can't get it right The input I've tried is: 4 3 2 1 The output I got is: 2 3 4 1

First I tried with using only an array of int for storing the heap and it worked, then I changed and used an array of struct node, but the final heap isn't a minHeap

Here is the main code:

int main(){

    makeMinHeap(v,vSize-1); // v is the pointer to the array of struct node, and vSize is the 
                            // size of the array
}
    void makeMinHeap(struct node *h, int size) {
    for (int i = floor(size/2); i >= 0 ; i--) {
        heapify(h, i,size);
    }
}

void heapify(struct node *h, int i,int size) {
    int l = left(i);
    int r = right(i);

    int m = i;

    if (l < size && h[l].value < h[i].value) {
        m = l;
    }
    else if (r < size && h[r].value < h[i].value) {
        m = r;
    }

    if (m != i) {
        swap(&h[m].value, &h[i].value);
        heapify(h, m, size);
    }

}

int left(int i) { return 2 * i; }

int right(int i) { return (2 * i + 1); }

void swap(int *x, int *y) { 
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

Answer 1

Here are some of the issues:

• The first (left) child of a node is not at i*2, but at i*2+1. The right child is at i*2+2.
• The else if condition in heapify should really be a separate if, and you don't want to compare with h[i].value but with h[m].value, since you want to compare with the least value so far (which might be at the left child)
• As vSize is the size of the array, you should not make the initial call with makeMinHeap(v, vSize-1), as you will then never look at the last value in the array. The -1 makes sense only for the heapify loop, which indeed can start at i = floor((size-1)/2), and so that subtraction should only be applied there.

Here are the relevant functions that needed correction:

int left(int i)  { return 2 * i + 1; } // corrected
int right(int i) { return 2 * i + 2; } // corrected

void heapify(struct node *h, int i, int size) {
    int l = left(i);
    int r = right(i);
    int m = i;

    if (l < size && h[l].value < h[i].value) {
        m = l;
    } // Not else-if here
    if (r < size && h[r].value < h[m].value) { // h[m]!
        m = r;
    }
    if (m != i) {
        swap(&h[m].value, &h[i].value);
        heapify(h, m, size);
    }
}

void makeMinHeap(struct node *h, int size) {
    for (int i = floor((size-1)/2); i >= 0 ; i--) { // -1 here
        heapify(h, i, size);
    }
}

int main(){
    int vSize = 4;
    struct node v[4] = {4, 3, 2, 1};
    makeMinHeap(v, vSize); // No -1 here! 
    for (int i = 0; i < vSize; i++) printf("%i ", v[i].value);
    printf("\n");    
}