I am trying to split set of numbers to 2 different heaps, from their middle value. I used heap data structure to do this. i.e Input is 10 in this example. Apparently I am making some mistake while allocating memory, it gives the following output when I try to allocate dynamically:
[ 4 3 2 0 1 ]
[ 0 0 0 0 0 ]
why the second heap is always 0 ?
Because if I uncomment the static memory allocation and use it instead, it gives true output which is:
[ 4 3 2 0 1 ]
[ 9 8 7 5 6 ]
I have tested my heap and other parts well enough, I am pretty sure the problem is on memory allocation but I couldn't find out where the mistake is.
int main(int argc, char *argv[])
{
int M = atoi(argv[1]);
int pq_1_size = M / 2;
int pq_2_size = M - pq_1_size;
int *a;
int *b;
a = (int *)malloc(pq_1_size * sizeof(int));
b = (int *)malloc(pq_2_size * sizeof(int));
for (int i = 0; i < pq_1_size; i++) {
a[i] = i;
}
for (int j = pq_1_size; j < M; j++) {
b[j] = j;
}
//int a[5] = { 0, 1, 2, 3, 4 }; // if I use this section instead it works fine.
//int b[5] = { 5, 6, 7, 8, 9 }; // if I use this section instead it works fine.
Heap someHeap = { 0, {0} };
Heap *A = &someHeap;
buildHeap(A, a, pq_1_size);
//buildHeap(A, a, 5);
print(A);
printf("\n");
Heap anotherHeap = { 0, {0} };
Heap *B = &anotherHeap;
buildHeap(B, b, pq_2_size);
//buildHeap(B, b, 5);
print(B);
return 0;
}
Below is the heap code:
#define HEAPSIZE 500
#define left(i) ((i)<<1)
#define right(i) (((i)<<1)+1)
#define parent(i) ((i)>>1)
typedef struct {
int size;
int element[HEAPSIZE];
} Heap;
//Swaps the values of two ints a and b
void swap(int * a, int * b) {
int temp;
temp = * a;
* a = * b;
* b = temp;
}
//Ensures that the max heap property in heap A is satisfied at and below index i
void makeHeap(Heap * A, int i) {
int largest = A->element[i];
int position = i;
int l = left(i);
if(l <= A->size && A->element[l] > largest) {
largest = A->element[l];
position = l;
}
int r = right(i);
if(r <= A->size && A->element[r] > largest) {
largest = A->element[r];
position = r;
}
if(i != position) {
swap(&A->element[i], &A->element[position]);
makeHeap(A, position);
}
}
//Get the maximum value in the heap A
int extractMax(Heap * A) {
if(!A->size) {
puts("error: heap empty");
return 0;
}
int max = A->element[0];
swap(&A->element[0], &A->element[A->size]);
--A->size;
makeHeap(A, 0);
return max;
}
//Increase the key of the ith element in heap A to be k
void increaseKey(Heap * A, int i, int k) {
if(A->element[i] >= k) {
printf("error: %d is less than the key of %d\n", k, i);
return;
}
int position = i;
while(position != 0 && A->element[parent(position)] < k) {
A->element[position] = A->element[parent(position)];
position = parent(position);
}
A->element[position] = k;
}
//Inserts the value i into the heap A
void insert(Heap * A, int i) {
if(A->size >= HEAPSIZE) {
printf("error: heap full\n");
return;
}
A->element[A->size] = INT_MIN;
increaseKey(A, A->size, i);
++A->size;
}
//Prints the heap A as an array
void print(Heap * A) {
int i = 0;
printf("[ ");
for(i = 0; i < A->size; i++) {
printf("%d ", A->element[i]);
}
printf("]\n");
}
//Makes a heap out of an unsorted array a of n elements
void buildHeap(Heap * A, int * a, int n) {
if(n > HEAPSIZE) {
printf("error: too many elements\n");
return;
}
if(A->size) {
printf("error: heap not empty\n");
return;
}
int nbytes = n * sizeof(int);
memcpy(A->element, a, nbytes);
A->size = n;
int i = 0;
for(i = A->size/2; i >= 0; i--) {
makeHeap(A, i);
}
}
