Need help pinpointing a problem

I just cant figure out where i did wrong in my maxheap implementation... i didnt even discover it had a problem until i changed it to a minheap to use in a disjktra

i'm pretty sure it's related to the fact that arrays in C start at 0, but i cant seem to find the error... so i tought an outsider eye couldnt pinpoint it since i probably keep making the same error over and over again

here's the code

i apreciated all your help

*Edited code to hv a main and it now shows my problem*

Code:

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

#define LEFT(x)  (2*x)                         /* left child of a node */
#define RIGHT(x) ((2*x)+1)                     /* right child of a node */
#define PARENT(x) (x/2)                        /* parent of a node */
#define SWAP(tmp,x,y) tmp = x ; x = y ; y = tmp  /* swap to variables */

void max_heapify(int A[], int i, int size) {

	int l, r, largest, temp;

	l = LEFT(i);
	r = RIGHT(i);

	if(l <= size && A[l-1] > A[i-1])
		largest = l;
	else largest = i;

	if(r <= size && A[r-1] > A[largest-1])
		largest = r;

	if(largest != i) {
		SWAP(temp, A[i-1], A[largest-1]);
		max_heapify(A, largest, size);
	}
}

void build_max_heap(int A[], int size) {
	
	int i;

	for(i = (size/2); i>0; i--)
		max_heapify(A, i, size);

}

int heap_maximum(int A[]) {
	return A[0];
}

int heap_extract_max(int A[], int *size) {

	int max;

	if(*size < 1) {
		printf("Heap underflow.\n");
		return -1;
	}

	max = A[0];
	A[0] = A[(*size)-1];
	*size = (*size)-1;
	max_heapify(A, 1, *size);

	return max;
}

void heap_increase_key(int A[], int i, int key) {

	int temp;

	if(key<A[i]) {
		printf("New key is smaller than current key.\n");
		return;
	}
	
	A[i] = key;

	while(i > 0 && A[PARENT(i)] < A[i]) {
		SWAP(temp, A[i], A[PARENT(i)]);
		i = PARENT(i);
	}
}

void max_heap_insert(int A[], int *size, int max_size, int key) {

	if(*size >= max_size) {
		printf("Heap capacity exceeded, new element not added.\n");
		return;
	}

	*size = (*size)+1;
	A[*size]=-1; /*should be - infinity*/
	heap_increase_key(A, *size, key);
}

int main(int argc, char *argv[]) {

	int maxsize, size, i;
	int *array;
	
	maxsize=size=5;
	i=0;
	array = malloc(maxsize*sizeof(int));
	

	while(i<maxsize) {
		array[i]=-1;
		i++;
	}

	array[0]=0;
	array[4]=7;
	array[3]=3;
	build_max_heap(array, size);
	for(i=0; i< size; i++)
		printf("&#37;i ", array[i]);
	printf("\n");

	heap_extract_max(array, &size);
	for(i=0; i< size; i++)
		printf("%i ", array[i]);
	printf("\n");

	max_heap_insert(array, &size, maxsize, 2);
	for(i=0; i< size; i++)
		printf("%i ", array[i]);
	printf("\n");

	heap_extract_max(array, &size);
	for(i=0; i< size; i++)
		printf("%i ", array[i]);
	printf("\n");

	max_heap_insert(array, &size, maxsize, 10);
	for(i=0; i< size; i++)
		printf("%i ", array[i]);
	printf("\n");

	free(array);
	return 0;

}

> i'm pretty sure it's related to the fact that arrays in C start at 0, but i cant seem to find the error
Some signs of where you could be going wrong
- using <= rather than < for checking whether something is a valid subscript.
- excessive use of -1 to convert a 1-based index into a 0-based index.

I have to say that your use of 'i' and 'l' as variable names, and lots of '1' adjustments makes for very hard reading of the code.

It would also be useful to post a main() which calls these functions. Maybe they work just fine, and the problem is in the way you're calling them.

i edited it to have the necessary information to run the test that i'm failing... sorry for the crude main, but it does the job

end result after running it:

Code:

7 3 -1 0 -1
3 0 -1 -1
3 2 0 -1 -1
2 -1 0 -1
10 2 -1 -1 -1

as u can see, in the last insert i get 10 2 -1 -1 -1... but the result from the extract before it, as you can see is 2 -1 0 -1, so where did the 0 go? i cant seem to find any reason to my algorithm replacing the 0 with -1

also, i had to use the -1 since the way u discover the left and right is by multiplication, so 0 wouldnt work there.. so i call it with 1 and adjust with -1 later

anyone? i'm still stuck at this

*edit* well, i now know that the problem is in heap_increase_key...

Code:

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

#define LEFT(x)  (2*x)                         /* left child of a node */
#define RIGHT(x) ((2*x)+1)                     /* right child of a node */
#define PARENT(x) (x/2)                        /* parent of a node */
#define SWAP(tmp,x,y) tmp = x ; x = y ; y = tmp  /* swap to variables */

#define ARANGE(x,lim)   assert( (x)>=0 && (x)<lim )


void max_heapify(int A[], int i, int size) {

    int l, r, largest, temp;

    l = LEFT(i);
    r = RIGHT(i);

    ARANGE(l-1,size);
    ARANGE(i-1,size);
    if(l <= size && A[l-1] > A[i-1])
        largest = l;
    else largest = i;

    ARANGE(r-1,size);
    ARANGE(largest-1,size);
    if(r <= size && A[r-1] > A[largest-1])
        largest = r;

    if(largest != i) {
        ARANGE(i-1,size);
        ARANGE(largest-1,size);
        SWAP(temp, A[i-1], A[largest-1]);
        max_heapify(A, largest, size);
    }
}

I compiled with these ARANGE checks and got

Code:

$ ./a.exe
assertion "(l-1)>=0 && (l-1)<size" failed: file "foo.c", line 20

If you run this in the debugger, the debugger should catch the assert, and allow you to look around the code to figure out where it all went wrong (why is the subscript apparently out of range). When you understand why, then you can fix the code.

fixed the problem, thnx for all the help

one last question, i changed the heap to receive a array of structs instead of ints, and i'm having a problem that sometimes 1 insert changes 2 values... so i'm pretty sure it something related to the pointers

if the swap macro receives pointers instead of ints does it work? if not, could u explain me how to do it?

i'm doing something in the lines of A[*size-1]->value=10; and it's chaging both the *size-1 position of the array and another one at the same time...