0 Replies - 256 Views - Last Post: 10 June 2008 - 07:35 AM Rate Topic: -----

#1 born2c0de   User is offline

  • printf("I'm a %XR",195936478);
  • member icon

Reputation: 187
  • View blog
  • Posts: 4,673
  • Joined: 26-November 04

Heap Sort

Posted 10 June 2008 - 07:35 AM

Description: Implements Heap Sort
/* Written by Sanchit Karve (born2c0de)
   Contact me on born2c0de AT dreamincode DOT net
*/

#include <stdio.h>

#define HEAPSIZE 50
#define MAX 5

#define SHOWPASS

struct heap
{
       int a[HEAPSIZE];
       int index;
};
typedef struct heap Heap;

void print(Heap *p)
{
		int i;
		for(i=0;i<=p->index;i++)
			printf("%dt",p->a[i]);
}

void insertpq(Heap *p,int val)
{
	int i;
	if(p->index==HEAPSIZE-1)
		printf("n Heap is full");
	else
	{
		for(i=++p->index;i>0&&p->a[(i-1)/2]>val;i=(i-1)/2)
			p->a[i]=p->a[(i-1)/2];
		p->a[i]=val;
	}
}


int removeq(Heap *p)
{
	int value,temp,i;
	if(p->index==-1)
	{
		printf("n Heap is empty");
		return -1;
	}
	else
	{
		value=p->a[0];
		temp=p->a[p->index--];
		for(i=1;i<=p->index;i=2*i+1)
		{
			if(((i+1)<=p->index)&&(p->a[i]>p->a[i+1]))
				i++;
			if(p->a[i]<temp)
				p->a[(i-1)/2]=p->a[i];
			else
				break;
		}
		p->a[(i-1)/2]=temp;
		return value;
	}
}

int main()
{
           int arr[MAX];
           int i,n;
           Heap s;

           s.index=-1;
           
           printf("nEnter total elements (n < %d) : ",MAX);
           scanf("%d",&n);

		   printf("Enter %d Elements : ",n);
                  
           for(i=0;i<n;i++)
           {                           
                           scanf("%d",&arr[i]);
                           insertpq(&s,arr[i]);
#ifdef SHOWPASS
                           printf("nHEAP +%d : ",arr[i]);
                           print(&s);
#endif
           }
           
           printf("n ");
           i=0;
           while(s.index!=-1)
           {
                             arr[i]=removeq(&s);
#ifdef SHOWPASS
                             printf("nHEAP -%d : ",arr[i]);               
                             print(&s);
#endif
							 i++;
           }               
           
           printf("nSORTED : ");
           printf("n");
           for(i=0;i<n;i++)
                           printf("%dt",arr[i]);

		   printf("n");
           
           
           return 0;
}



Is This A Good Question/Topic? 0
  • +

Page 1 of 1