0

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];
		}
	}
}
4
Contributors
4
Replies
6
Views
7 Years
Discussion Span
Last Post by IsharaComix
0

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 by Adak: n/a

0

i'm using Dev C++

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

Edited by churni: n/a

0

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.

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.

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 topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.