// File: Heapsort.java
// A Java application to illustrate the use of a heapsort
// Additional javadoc documentation is available at:
// http://www.cs.colorado.edu/~main/docs/Heapsort.html
/******************************************************************************
* The Heapsort
Java application illustrates a heapsort.
* Part of the implementation (the makeHeap
and
* reheapifyDown
methods) is left
* as a student exercise.
*
*
Java Source Code for this class (without
* makeHeap
and reheapifyDown
:
*
* http://www.cs.colorado.edu/~main/applications/Heapsort.java
*
*
* @author Michael Main and (___student name___)
* (main@colorado.edu)
*
* @version Feb 10, 2016
******************************************************************************/
public class Heapsort
{
/**
* The main method illustrates the use of a heapsort to sort a
* small array.
* @param args
* not used in this implementation
**/
public static void main(String[ ] args)
{
final String BLANKS = " "; // A String of two blanks
int i; // Array index
int[ ] data = { 80, 10, 50, 70, 60, 90, 20, 30, 40, 0 };
// Print the array before sorting:
System.out.println("Here is the entire original array:");
for (i = 0; i < data.length; i++)
System.out.print(data[i] + BLANKS);
System.out.println( );
// Sort the numbers, and print the result with two blanks after each number.
heapsort(data, data.length);
System.out.println("After sorting, the numbers are:");
for (i = 0; i < data.length; i++)
System.out.print(data[i] + BLANKS);
System.out.println( );
}
/**
* This method cannot be used until the student implements
* makeHeap
and reheapifyDown
.
* Sort an array of integers from smallest to largest, using a heapsort
* algorithm.
* @param data
* the array to be sorted
* @param n
* the number of elements to sort, (from data[0]
* through data[n-1]
)
* Precondition:
* data
has at least n
elements.
* Postcondition:
* If n
is zero or negative then no work is done. Otherwise,
* the elements of data
have been rearranged so that
* data[0] <= data[1] <= ... <= data[n-1]
.
* @exception ArrayIndexOutOfBoundsException
* Indicates that data
has fewer than n
elements.
* */
public static void heapsort(int[ ] data, int n)
{
int unsorted; // Size of the unsorted part of the array
int temp; // Used during the swapping of two array locations
makeHeap(data, n);
unsorted = n;
while (unsorted > 1)
{
unsorted--;
// Swap the largest element (data[0]) with the final element of unsorted part
temp = data[0];
data[0] = data[unsorted];
data[unsorted] = temp;
reheapifyDown(data, unsorted);
}
}
private static void makeHeap(int[ ] data, int n)
// Precondition: data is an array with at least n elements.
// Postcondition: The elements of data have been rearranged so that the
// complete binary tree represented by this array is a heap.
{
System.err.println("The student needs to implement the makeHeap and");
System.err.println("reheapifyDown methods before the heapsort can be used.");
System.exit(0);
}
private static void reheapifyDown(int[ ] data, int n)
// Precondition: n > 0, and data is an array with at least n elements. These
// elements form a heap, except that data[0] may be in an incorrect
// location.
// Postcondition: The data values have been rearranged so that the first
// n elements of data now form a heap.
{
System.err.println("The student needs to implement the makeHeap and");
System.err.println("reheapifyDown methods before the heapsort can be used.");
System.exit(0);
}
}