Heap Sort Algorithm

11 12 2007

The heap sort does not require massive recursion or multiple arrays to work. This makes it an attractive option for very large data sets of millions of items.

The heap sort works as it name suggests – it begins by building a heap out of the data set, and then removing the largest item and placing it at the end of the sorted array. After removing the largest item, it reconstructs the heap and removes the largest remaining item and places it in the next open position from the end of the sorted array. This is repeated until there are no items left in the heap and the sorted array is full. Elementary implementations require two arrays – one to hold the heap and the other to hold the sorted elements.

To do an in-place sort and save the space the second array would require, the algorithm below “cheats” by using the same array to store both the heap and the sorted array. Whenever an item is removed from the heap, it frees up a space at the end of the array that the removed item can be placed in.

Heap Sort Routine

// array of integers to hold values
private int[] a = new int[100];

// number of elements in array
private int x;

// Heap Sort Algorithm
public void sortArray()
{
int i;
int temp;

for( i = (x/2)-1; i >= 0; i– )
{
siftDown( i, x );
}

for( i = x-1; i >= 1; i– )
{
temp = a[0];
a[0] = a[i];
a[i] = temp;
siftDown( 0, i-1 );
}
}

public void siftDown( int root, int bottom )
{
bool done = false;
int maxChild;
int temp;

while( (root*2 <= bottom) && (!done) )
{
if( root*2 == bottom )
maxChild = root * 2;
else if( a[root * 2] > a[root * 2 + 1] )
maxChild = root * 2;
else
maxChild = root * 2 + 1;

if( a[root] < a[maxChild] )
{
temp = a[root];
a[root] = a[maxChild];
a[maxChild] = temp;
root = maxChild;
}
else
{
done = true;
}
}
}

You can download the full code here, or the compiled code here.

further : http://www.publicjoe.f9.co.uk/

Advertisements

Actions

Information

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s




%d bloggers like this: