Heap Sort - Java Implementation

This section provides a tutorial on how to implement the Heap Sort algorithm in Java.

Here is my Java implementation of Heap Sort algorithm:

```/* HyArrays.java
* This class contains sorting methods similar to java.util.Arrays.sort().
* All sorting methods should have a signature of
* %Sort(Object[] a, int fromIndex, int toIndex)
* where "fromIndex" is inclusive, and "toIndex" is exclusive.
*/
public class HyArrays {
public static void heapSort(HyObject[] a, int fromIndex,
int toIndex) {
HyObject d;
int n = toIndex - fromIndex;
for (int i=n/2; i>=1; i--) {
downHeap(a,i,n,fromIndex);
}
for (int i=n; i>1; i--) {
d = a[fromIndex];
a[fromIndex] = a[fromIndex+i-1];
a[fromIndex+i-1] = d;
downHeap(a,1,i-1,fromIndex);
}
}
private static void downHeap(HyObject[] a, int i, int n,
int fromIndex) {
HyObject d = a[fromIndex+i-1];
int child;
while (i<=n/2) {
child = 2*i;
if (child<n && (a[fromIndex+child-1]).compareTo(
a[fromIndex+child])<0) {
child++;
}
if (d.compareTo(a[fromIndex+child-1])>=0) break;
a[fromIndex+i-1] = a[fromIndex+child-1];
i = child;
}
a[fromIndex+i-1] = d;
}
}
```

Note that:

• Data elements are stored in the input array between "fromIndex" and "toIndex", and it is easier to manage a heap array with index from "1" to "n", so I have to do some index conversions like "fromIndex+i-1".

In case you are using older versions of Java that support only the raw "Comparable" interface type, here is my old implementation:

```/* HyArrays.java
* This class contains sorting methods similar to java.util.Arrays.
* All sorting methods should have a signature of
* %Sort(Object[] a, int fromIndex, int toIndex)
* where "fromIndex" is inclusive, and "toIndex" is exclusive.
*/
public class HyArrays {
public static void heapSort(Object[] a, int fromIndex,
int toIndex) {
Object d;
int n = toIndex - fromIndex;
for (int i=n/2; i>=1; i--) {
downHeap(a,i,n,fromIndex);
}
for (int i=n; i>1; i--) {
d = a[fromIndex];
a[fromIndex] = a[fromIndex+i-1];
a[fromIndex+i-1] = d;
downHeap(a,1,i-1,fromIndex);
}
}
private static void downHeap(Object[] a, int i, int n,
int fromIndex) {
Comparable d = (Comparable)a[fromIndex+i-1];
int child;
while (i<=n/2) {
child = 2*i;
if (child<n && ((Comparable)a[fromIndex+child-1]).compareTo(
a[fromIndex+child])<0) {
child++;
}
if (d.compareTo(a[fromIndex+child-1])>=0) break;
a[fromIndex+i-1] = a[fromIndex+child-1];
i = child;
}
a[fromIndex+i-1] = d;
}
}
```