Sorting Algorithm Tutorials - Herong's Tutorial Examples - 6.12, by Herong Yang
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. * Copyright (c) 2011 HerongYang.com. All Rights Reserved. */ 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:
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. * Copyright (c) 2011 HerongYang.com. All Rights Reserved. */ 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; } }
Table of Contents
Introduction of Sorting Algorithms
Java API for Sorting Algorithms
Insertion Sort Algorithm and Java Implementation
Selection Sort Algorithm and Java Implementation
Bubble Sort Algorithm and Java Implementation
Quicksort Algorithm and Java Implementation
Merge Sort Algorithm and Java Implementation
►Heap Sort Algorithm and Java Implementation
Heap Sort - Algorithm Introduction
►Heap Sort - Java Implementation
Heap Sort - Implementation Improvements
Shell Sort Algorithm and Java Implementation
Sorting Algorithms Implementations in PHP
Sorting Algorithms Implementations in Perl
Sorting Algorithms Implementations in Python