Showing posts with label tricky. Show all posts
Showing posts with label tricky. Show all posts

Saturday, August 9, 2014

Program for heap sort

Program for Heap Sort. Kinda tricky program. If you need help, comment below

#include<stdio.h> int tree[20],n,ah[20],c=0; void build(int m,int item) { int ptr,par,f=0; m=m+1; ptr=m; while(ptr>1) { par=ptr/2; if(item<=tree[par]) { tree[ptr]=item; f=1; break; } tree[ptr]=tree[par]; ptr=par; } if(f==0) tree[1]=item; } void delheap(int k,int m) { int left,right,ptr,last,i; ah[k]=tree[1]; last=tree[m]; m=m-1; ptr=1; left=2; right=3; while(right<=m) { if((last>=tree[left])&&(last>=tree[right])) { tree[ptr]=last; return; } if(tree[right]<=tree[left]) { tree[ptr]=tree[left]; ptr=left; } else { tree[ptr]=tree[right]; ptr=right; } left=2*ptr; right=left+1; } if((left==m)&&(last<tree[left])) { tree[ptr]=tree[left]; ptr=left; } tree[ptr]=last; c++; printf("\n\nPass %d: ",c); for(i=1;i<=m;i++) printf("%d ",tree[i]); } main() { int i,j; printf("\nEnter total number of elements:"); scanf("%d",&n); printf("\nEnter elements to be inserted : "); for(i=1;i<=n;i++) scanf("%d",&tree[i]); for(i=1;i<n;i++) build(i,tree[i+1]); printf("\n\nHeap : "); for(i=1;i<=n;i++) printf("%d ",tree[i]); for(i=n,j=1;i>1;i--,j++) delheap(j,i); if(i==1) ah[n]=tree[1]; printf("\n\nHeap sort : "); for(i=1;i<=n;i++) printf("%d ",ah[i]); }