Need help pinpointing a problem

This is a discussion on Need help pinpointing a problem within the C Programming forums, part of the General Programming Boards category; I just cant figure out where i did wrong in my maxheap implementation... i didnt even discover it had a ...

  1. #1
    Registered User
    Join Date
    May 2007
    Posts
    4

    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;
    
    }
    Last edited by alwaystired; 05-12-2007 at 11:15 AM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,822
    > 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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    May 2007
    Posts
    4
    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

  4. #4
    Registered User
    Join Date
    May 2007
    Posts
    4
    anyone? i'm still stuck at this

    *edit* well, i now know that the problem is in heap_increase_key...
    Last edited by alwaystired; 05-13-2007 at 11:18 AM.

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,822
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  6. #6
    Registered User
    Join Date
    May 2007
    Posts
    4
    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...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Need help understanding a problem
    By dnguyen1022 in forum C++ Programming
    Replies: 2
    Last Post: 04-29-2009, 05:21 PM
  2. Memory problem with Borland C 3.1
    By AZ1699 in forum C Programming
    Replies: 16
    Last Post: 11-16-2007, 11:22 AM
  3. Someone having same problem with Code Block?
    By ofayto in forum C++ Programming
    Replies: 1
    Last Post: 07-12-2007, 09:38 AM
  4. A question related to strcmp
    By meili100 in forum C++ Programming
    Replies: 6
    Last Post: 07-07-2007, 03:51 PM
  5. WS_POPUP, continuation of old problem
    By blurrymadness in forum Windows Programming
    Replies: 1
    Last Post: 04-20-2007, 07:54 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21