# heap sort

This is a discussion on heap sort within the C Programming forums, part of the General Programming Boards category; Hi,people! I was looking through adjustment of heap but the explanation is too difficult for me. I'll appreciate if somebody ...

1. ## heap sort

Hi,people!

I was looking through adjustment of heap but the explanation is too difficult for me.
I'll appreciate if somebody can explane and show easy and clear model of heap sorting.

Thanks!

2. A heap is a structure where items are stored in an array in such a way so that each item is guaranteed to be larger than the items at two other specific locations. Each of those items are also larger than two more, and so on. It's a binary structure compressed into a linear array:
Code:
```         X
/     \
T         O
/ \       / \
G   S     M   N
/\   /\   /
A  E R  A I

1 2 3 4 5 6 7 8 9 10 11 12
X T O G S M N A E R  A  I```
The heapsort is a method of building a heap and then removing the largest element repeatedly until the data is sorted. Here's the basic idea:
Code:
```#include <stdio.h>

#define less(a, b) ((a) < (b))

static void exchange ( int *a, int *b )
{
int t = *a;
*a = *b;
*b = t;
}

static void fixDown ( int *a, int k, int N )
{
int j;
while ( 2 * k <= N ) {
j = 2 * k;
if ( j < N && less ( a[j], a[j+1] ) )
j++;
if ( !less ( a[k], a[j] ) )
break;
exchange ( &a[k], &a[j] );
k = j;
}
}

static void heapsort ( int *a, int l, int r )
{
int k, N = r - l + 1;
int *pq = a + l - 1;
for ( k = N / 2; k >= 1; k-- )
fixDown ( pq, k, N );
while ( N > 1 ) {
exchange ( &pq[1], &pq[N] );
fixDown ( pq, 1, --N );
}
}

int main ( void )
{
int i;
int a[10] = {8,3,9,1,0,5,9,3,6,4};
heapsort ( a, 0, 9 );
for ( i = 0; i < 10; i++ )
printf ( "%d ", a[i] );
printf ( "\n" );
return 0;
}```
-Prelude

Popular pages Recent additions