hi guys,

i'm frustrated at my piece of code for a heap sort function. i believe everything is correct but i am a hardcore beginner at c. i have made a rand.txt file with some floats in it in the form;
91.175598
68.562500
96.664803
29.593500
43.156502
34.241001
59.178200
85.542702
81.852798
23.628799

but when i run it, its not reading them numbers and is just writing out 5000 (max array size) values of 0.0000. any ideas what i am doing wrong?

thanks

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

#define MAXHEAP 100
#define N 5000
typedef char DATA ;

typedef struct heap {
	float a[N];
	int size;
} HEAP;


float gettop(HEAP *h); /* returns and removes top element from heap */
void insert(HEAP *h, float d); /* inserts d into heap */
int left(HEAP *h,int i); /* computes and returns i's left child index */
int right(HEAP *h,int i); /* computes and returns i's right child index */
int parent(HEAP *h,int i); /* computes and returns i's parent index */
int cmp(float a,float b); /* compares a and b, 
			   returns -1 if(a<b), 
			   returns 0  if(a == b) or
			   return  +1 if(a>b) */

int main(void){
	HEAP h; 
	int i,j;
    char buff[BUFSIZ];
    float a[N];
    FILE *in;
    in=fopen("rand.txt","r");
  
    h.size=0; /* empty heap */
	for(i=0;i<BUFSIZ;i++){ /* assemble heap */
		if(a[i]!=' '){ /* ignore spaces */
			insert(&h,(float)a[i]);
			printf("%f",a[i]);
		}
	}
	printf("\ncreated heap\n");
		
	/* print heap out */
	for(j=0;j<=i;j++){
         if(j%20==0){
    while(h.size)
		printf("%f\n",(float)gettop(&h));
}}	

    getch();
    system("cls");
    return 0;

}

int left(HEAP *h,int i){ /* computes and returns i's left child index */
	if(i>h->size||i<1){
		printf("left: impossible index %d\n",i);
		exit(1);
	}
	if(i*2 > h->size)
		return 0; /* i on lowest layer has no left child */
	return i*2; /* return index of left child */ 
}

int right(HEAP *h,int i){ /* computes and returns i's right child index */
	if(i>h->size||i<1){
		printf("right: impossible index %d\n",i);
		exit(1);
	}
	if(i*2+1 > h->size)
		return 0; /* i on lowest layer has no right child */
	return i*2+1; /* return index of right child */ 
}
	

int parent(HEAP *h,int i){ /* computes and returns i's parent index */
	if(i>h->size||i<1){
		printf("right: impossible index %d\n",i);
		exit(1);
	}
	if(i==1)
		return 0; /* top has no parent */
	else
		return i/2;
}

int cmp(float a,float b){ /* compares a and b, 
			   returns -1 if(a<b), 
			   returns 0  if(a == b) or
			   return  +1 if(a>b) */
	if(a<b) return -1;
	else if(a==b) return 0;
	else return 1;
}

float gettop(HEAP *h){ /* returns and removes top element from heap */
	float top,last;
	int i,j,k;	
	if(h->size == 0){ /* error case for empty heap */
		printf("gettop: empty heap\n");
		exit(1);
	}
	top=h->a[1];  	
	if(h->size == 1){ /* special case for heap with only 1 node */
		h->size--;
		return top; /* heap is now empty */
	} else {
		/* unlink and store last node in heap */
		last=h->a[h->size--];
		/* need to rearrange heap following extract, */
		i=1;
		while(1){
			j=left(h,i);
			k=right(h,i);
			if(j && k){ /* i has both left and right children */
				if(cmp(last,h->a[j])<0 &&
				   cmp(last,h->a[k])<0)
					break; /* heap OK so quit loop */
				if(cmp(h->a[j],h->a[k])<=0){ 
					/* move hole down to left */
					h->a[i]=h->a[j];
					i=j;
				} else {	
					/* move hole down to right */
					h->a[i]=h->a[k];
					i=k;
				}
			} else if(j){ /* i has a left but no right child */
				if(cmp(last,h->a[j])<0)
					break; /* heap OK, quit loop */
				/* move hole to left */
				h->a[i]=h->a[j];
				i=j;
			} else  /* node i now at bottom of heap */
				break;
		}
		/* replace unlinked last node in hole now at lowest layer */
		h->a[i]=last;
		return top;
	}	
}
	
	
void insert(HEAP *h, float d){ /* inserts d into heap */
	int i,j;
	if(h->size==0){ /* special case of empty heap */
		h->size++;
		h->a[1]=d;
	} else {
		h->size++; /* create hole at bottom of heap */
		i=h->size;
		while(1){ /* move hole to position where d can be inserted */
			j=i;
			i=parent(h,i);
			if(!i){ /* hole must now be at top so insert here */
				h->a[1]=d;
				return;
			}
			if(cmp(d,h->a[i])>=0){ 
				/* heap OK so insert below parent here */
				h->a[j]=d;
				return;
			}
			/* bubble parent value down, and hole up */
			h->a[j]=h->a[i];
		}
	}
}

What's your compiler?

Just for giggles, try this:

float a[N] = {0.0};

and you can delete char buff[] because it's never used.

Edited 6 Years Ago by Adak: n/a

i'm using Dev C++

i tried doing what you said and it makes no difference to the output.

Edited 6 Years Ago by churni: n/a

1) You should not need to initialize the thing you are calling heap, other than setting size=0.
2) "heap" is the name we use for "malloc space", so your use of the term is non-standard, and this is homework, I pity your grade.
3) There is no code that reads the file. There is a line that opens it, but no code that reads it or closes it.
4) When debugging, use a smaller example. Try 5 instead of 5000, for example, and step through the code logically in your head, then in the debugger, observing that every variable is doing the right thing.

2) "heap" is the name we use for "malloc space", so your use of the term is non-standard, and this is homework, I pity your grade.
3) There is no code that reads the file. There is a line that opens it, but no code that reads it or closes it.

The "Heap" is also a very ubiquitous data structure, and is used in several academic papers, in addition to my research project. :) http://en.wikipedia.org/wiki/Heap_(data_structure)

But point #3 is right on the mark. All your code is missing is the proper reading. The sorting is working on my machine. Just replace your for loop with the below code.

while ( fscanf( in, "%f", a ) == 1 )
    {
        insert( &h, a[0] );
        i++;
    }

There are lots of style issues, but it looks like you've got heap-sort downpat. Good work!

This article has been dead for over six months. Start a new discussion instead.