0

I want to create a binary heap with custom element, and the heap uses an array of struct Elem for store the data. But after the insertion, some data are lost, in this case the key value.

#include <stdlib.h>
#include <stdio.h>

#define DEFAULT_CAPACITY    16
#define VALS 10

const int values[VALS] = {1, 2, 3, 4, 7, 8, 9, 10, 14, 16};

typedef int (*compareFunction)(const void *, const void *);

typedef struct Elem {
    void    *key;
    void    *value;
} Elem;

typedef struct Heap {
    unsigned int    size;
    unsigned int    capacity;
    Elem            **array;
    compareFunction compare;
} Heap;

Heap *hpCreate(compareFunction compare)
{
    Heap *heap;

    heap = (struct Heap *) malloc(sizeof(struct Heap));
    if (heap == NULL) return NULL;

    if ((heap->array = (struct Elem **) malloc(0)) == NULL) {
        free(heap);
        return NULL;
    }

    heap->size = 0;
    heap->capacity = DEFAULT_CAPACITY;
    heap->compare = compare;

    return heap;
}

Elem *hpCreateElem(void *key, void *value)
{
    Elem *el;

    el = (struct Elem *) malloc(sizeof(struct Elem));
    if (el == NULL) return NULL;

    el->key = key;
    el->value = value;

    return el;
}

void hpInsert(Heap *hp, void *key, void *value)
{
    Elem *el, *par;
    int pos;

    pos = hp->size++;
    el = hpCreateElem(key, value);
    par = hp->array[pos/2];

    while (pos > 1 && hp->compare(el->key, par->key) > 0) {
        hp->array[pos] = hp->array[pos/2];
        pos = pos/2;
        par = hp->array[pos/2];
    }

    hp->array[pos] = el;
}

int compare_int_ptr(const void *ptr1, const void *ptr2)
{
    int v1 = *((int *) ptr1); 
    int v2 = *((int *) ptr2);

    if (v1 == v2)
        return 0;
    else
        return (v1 > v2) ? 1 : -1;
}

int main()
{
    Heap *hp;
    Elem *el;
    int i;

    hp = hpCreate(compare_int_ptr);

    for (i = 0; i < VALS; i++) {
        hpInsert(hp, (void *) &values[i], (void *) &values[i]);
    }

    for (i = 0; i < VALS; i++) {
        el = hp->array[i];
        printf("%d\n", *((int *) el->key));
    }

    return 0;
}

the output produced is

4196700
16
14
9
10
4
3
8
17231984
7

instead of the binary heap array correctly ordered as 16 9 14 7 4 8 10 3 2 1

3
  • 1
    I would postulate malloc(0) and DEFAULT CAPACITY 16 would seem to be in direct contradiction to each other. Not sure what you're trying to do, but I'm confident malloc(0) isn't going to get you there. Commented Jun 26, 2016 at 10:24
  • 1
    Adding to the malaise, your while-condition is wrong as well. Pretty sure you want while (pos > 0 , not while (pos > 1 Commented Jun 26, 2016 at 10:32
  • Somehow I read Heap as Hash and I was really confused by what the code was doing. Commented Jun 26, 2016 at 10:44

1 Answer 1

2

Since you're telling the container you allocated DEFAULT_CAPACITY elements:

heap->capacity = DEFAULT_CAPACITY;

then:

malloc(0)

should be

malloc(DEFAULT_CAPACITY * sizeof(Elem*))

The line:

par = hp->array[pos/2];

is reading an uninitialized object.

Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.