error creating a heap using array

Question

I'm trying to create a Binary Min Heap in C using arrays. I wrote the code and tried multiple times to execute it with "pen and paper" and it seems to work. Can you please help me to understand why it fails instead?

Here is the library code:

#include <stdlib.h>

void swapInt(int *a, int *b) {
    int aux = *a;
    *a = *b;
    *b = aux;
}

typedef struct intHeapArray {
    int *array;
    int size;
} IntHeapArray;

IntHeapArray newIntHeapArray (int dim) {
    IntHeapArray new;
    new.array = (int*) malloc(sizeof(int)*dim);
    new.size = 0;
    return new;
}

int findFather (int index) {
    return (index - 1) / 2;
}

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

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

int minFatherChilds (IntHeapArray h, int index) {
    int leftchild = findLeftChild(index);
    int rightchild = findRightChild(index);
    if (rightchild >= h.size)
        rightchild = leftchild;
    if (h.array[index] > h.array[leftchild])
        index = leftchild;
    if (h.array[index] > h.array[rightchild])
        index = rightchild;
    return index;
}

void reorganizeIntHeapArray (IntHeapArray *h, int index) {
    int father, leftchild, child;
    father = findFather(index);
    while (index > 0 && h->array[index] < h->array[father]) {
        swapInt(&h->array[index], &h->array[father]);
        index = father;
    }
    leftchild = findLeftChild(index);
    while (leftchild < h->size && index != minFatherChilds(*h, index)) {
        child = minFatherChilds(*h, index);
        swapInt(&h->array[index], &h->array[child]);
        index = child;
    }
}

void enqueueIntHeapArray (IntHeapArray *h, int val) {
    h->array[h->size] = val;
    h->size++;
    reorganizeIntHeapArray(h, h->size - 1);
}

Here is the calling from the main script:

#include <stdio.h>
#include "heap.h"

void printIntArray (int *a, int dim) {
    int i;
    printf("[");
    for (i = 0; i < dim - 1; i++)
        printf("%d, ", a[i]);
    printf("%d]\n", a[dim-1]);
}

int main () {
    IntHeapArray h;
    int n, i, val;

    printf("How many value would you like to add to the heap? ");
    scanf("%d", &n);

    h = newIntHeapArray(n);

    printf("Insert values:\n");
    for (i = 0; i < n; i++) {
        scanf("%d", &val);
        enqueueIntHeapArray(&h, val);
    }

    printf("This is your heap:\n");
    printIntArray(h.array, h.size);

    return 0;
}

The code compiles. Try it with this input: 6 3 8 9 2 0. It will print: [3, 2, 0, 9, 6, 8] that is obviously wrong. But I don't really understand where I'm wrong.

Asking strangers to spot errors in your code by inspection is not productive. You should use the debugger to step through your program and identify where its behaviour diverges from what you expect. — Oliver Charlesworth
– Oliver Charlesworth, Commented Jun 9, 2012 at 22:25
What do you think it should print? Why didn't you say so in the question? It is a good idea to be precise like that. — Jonathan Leffler
– Jonathan Leffler, Commented Jun 9, 2012 at 22:28
I didn't wrote what it should print because I linked the page about Binary Min Heap. The output should be: [0, 3, 2, 9, 6, 8]. This is according to the "pen and paper" execution (that I hope it's right). For sure, I should have 0 as first value. The lowest value has to be the first in this data structure. — Zagorax
– Zagorax, Commented Jun 10, 2012 at 2:24
People don't want to have to look elsewhere when the information can easily be included in the question. I assumed, without looking, that it is simply a link to Wikipedia or something similar (it is actually Wikipedia). But if you document what you think you should be getting, it reassures us that you are seeking the correct result. It is far from unheard of for people to be expecting the wrong result. — Jonathan Leffler
– Jonathan Leffler, Commented Jun 10, 2012 at 13:54

Zagorax · Accepted Answer · 2012-06-22 10:03:13Z

I found the error. The reorganize heap function has to be changed into:

void reorganizeIntHeapArray (IntHeapArray *h, int index) {
    int father, leftchild, child;
    father = findFather(index);
    while (index > 0 && h->array[index] < h->array[father]) {
        swapInt(&h->array[index], &h->array[father]);
        index = father;
        father = findFather(index);
    }
    leftchild = findLeftChild(index);
    while (leftchild < h->size && index != minFatherChilds(*h, index)) {
        child = minFatherChilds(*h, index);
        swapInt(&h->array[index], &h->array[child]);
        index = child;
        leftchild = findLeftChild(index);
    }
}

I was updating only the index value and not the father ones. So after the first switch, it compares h->array[index] with itself and not with its new father.

EDIT: It was still wrong. I did in the second while the same error I did in the first one. I wasn't updating leftchild value. Now it should be correct.

Collectives™ on Stack Overflow

error creating a heap using array

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related