Sunday, October 14, 2012

Implementation of Heap Sort


#include<stdio.h>

#define LEFT(i) 2*i+1
#define RIGHT(i) 2*i+2

void maxHeapify(int a[],int p,int len){
int max = p;
int temp;
if(LEFT(p) < len && a[LEFT(p)] > a[p]){
max = LEFT(p);
}
if(RIGHT(p) < len && a[RIGHT(p)] > a[max]){
max = RIGHT(p);
}
if(max != p){
temp = a[max];
a[max] = a[p];
a[p] = temp;
maxHeapify(a,max,len);
}
}

void buildHeap(int a[],int len){
int i;
for(i=(len-2)/2;i>=0;i--){
maxHeapify(a,i,len);
}
}

void heapSort(int a[],int len){
buildHeap(a,len);
int i,temp;
int heapLen = len;
for(i=0;i<len;i++){
temp = a[0];
a[0] = a[heapLen-1];
a[heapLen-1] = temp;
heapLen--;
maxHeapify(a,0,heapLen);
}
}

void printSorted(int a[],int len){
int i;
for(i=0;i<len;i++){
printf("%d\t",a[i]);
}
}

int main(){
int a[] = {9,8,7,6,5,4,3,2,1};
int len = sizeof(a)/sizeof(a[0]);
heapSort(a,len);
printSorted(a,len);
return 0;
}

No comments:

Post a Comment