Thread: 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.

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.