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
malloc(0)andDEFAULT CAPACITY 16would seem to be in direct contradiction to each other. Not sure what you're trying to do, but I'm confidentmalloc(0)isn't going to get you there.while (pos > 0, notwhile (pos > 1HeapasHashand I was really confused by what the code was doing.