ASP.Net-Heap Sort

Heap Sort

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 Code

// 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;
    }
  }
}