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;

}