#include<stdio.h> #include<stdlib.h> #include<conio.h>
void heapsort (int[], int); void siftdown (int[], int, int);
int main (void) { clrscr(); int a[5] = { 44, 22, 66, 77, 11 }; int i;
puts ("\n Before Sorting:: "); for (i = 0; i < 5; i++) printf ("%d\t", a[i]);
heapsort (a, 5);
puts ("\n After Sorting:: "); for (i = 0; i < 5; i++) printf ("%d\t", a[i]);
puts (""); getch(); return (EXIT_SUCCESS);
}
void heapsort (int a[5], int size) { int i, temp;
/* * heap creation */
for (i = size / 2; i >= 0; i--) { siftdown (a, i, size - 1); }
for (i = (size - 1); i >= 1; i--) { temp = a[0]; a[0] = a[i]; a[i] = temp; siftdown (a, 0, i - 1); } /*finding the max element & putting in last pos */
}
void siftdown (int a[5], int r, int b) { int done, maxchild, temp; done = 0;
while ((r * 2 <= b) && (!done)) { if (r * 2 == b) maxchild = r * 2; else if (a[r * 2] > a[r * 2 + 1]) maxchild = r * 2; else maxchild = r * 2 + 1;
/*check if root element < max child element,if it so swap, * set root pos = max child pos * */
if (a[r] < a[maxchild]) { temp = a[r]; a[r] = a[maxchild]; a[maxchild] = temp; r = maxchild; } else done = 1;
} }
//done by Hacker
|