Heap Sort Implementation in Java

Heapsort is one of the best general-purpose sorting algorithms, a comparison sort and part of the selection sort family. Although somewhat slower in practice on most machines than a good implementation of quicksort, it has the advantages of worst-case O(n log n) runtime and being an in-place algorithm. Heapsort is not a stable sort.

The following code shows how to implement heap sort in Java.

/**
* Standard heapsort.
* @param a an array of Comparable items.
*/
public static void heapsort( Comparable [ ] a )
{
for( int i = a.length / 2; i >= 0; i-- ) /* buildHeap */
percDown( a, i, a.length );
for( int i = a.length - 1; i > 0; i-- )
{
swapReferences( a, 0, i ); /* deleteMax */
percDown( a, 0, i );
}
}

/**
* Internal method for heapsort.
* @param i the index of an item in the heap.
* @return the index of the left child.
*/
private static int leftChild( int i )
{
return 2 * i + 1;
}

/**
* Internal method for heapsort that is used in
* deleteMax and buildHeap.
* @param a an array of Comparable items.
* @index i the position from which to percolate down.
* @int n the logical size of the binary heap.
*/
private static void percDown( Comparable [ ] a, int i, int n )
{
int child;
Comparable tmp;

for( tmp = a[ i ]; leftChild( i ) < i =" child">)
{
child = leftChild( i );
if( child != n - 1 && a[ child ].compareTo( a[ child + 1 ] ) < 0 )
child++;
if( tmp.compareTo( a[ child ] ) < 0 )
a[ i ] = a[ child ];
else
break;
}
a[ i ] = tmp;
}


/**
* Method to swap to elements in an array.
* @param a an array of objects.
* @param index1 the index of the first object.
* @param index2 the index of the second object.
*/
public static final void swapReferences( Object [ ] a, int index1, int index2 )
{
Object tmp = a[ index1 ];
a[ index1 ] = a[ index2 ];
a[ index2 ] = tmp;
}