Skip to content

Instantly share code, notes, and snippets.

@rice2007
Last active August 29, 2015 13:56
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save rice2007/9221749 to your computer and use it in GitHub Desktop.
Heapsort Comparator
package labthree.heapsort;
import java.util.Arrays;
import java.util.Comparator;
public class Driver {
private static long timeInitial;
private static long timeFinal;
private static long timeElapsed;
public static void main(String[] args) {
//Create comparators
Comparator minComp = new Lesser();
Comparator maxComp = new Greater();
int n;
for (int power = 4; power <= 10; power++) {
n = (int) Math.pow(2, power);
int[] maxArray = new int[n];
for (int i = 0; i < n; i++) {
maxArray[i] = (int) (Math.random() * (n + 1));
}
int[] minArray = Arrays.copyOf(maxArray, n);
//Sorts arrays using heapsort with comparator. Times them too.
System.out.println("MaxHeap Sort iteration " + power + ": " );
startTimer();
Heapsort.heapSort(maxArray, maxComp);
stopTimer();
System.out.println("MinHeap Sort iteration " + power + ": " );
startTimer();
Heapsort.heapSort(minArray, minComp);
stopTimer();
System.out.println("---------------------------------------\n");
}
}
/**
* Gets an arbitrary point in time expressed in nanoseconds.
*/
private static void startTimer() {
timeInitial = System.nanoTime();
}
/**
* Gets an arbitrary point in time expressed in nanoseconds then calculates the time elapsed since
* {@link #startTimer()} was last called.
*/
private static void stopTimer() {
timeFinal = System.nanoTime();
System.out.println("timeInitial: " + timeFinal);
System.out.println("timeFinal: " + timeFinal);
timeElapsed = (timeFinal - timeInitial);
System.out.println("timeElapsed: " + timeElapsed + "\n");
}
}
public class Heapsort {
private static int node;
private static int heapSize;
private static int left;
private static int right;
public static void heapSort(int[] array, Comparator comp) {
buildHeap(array, comp);
int temp;
for (int i = array.length - 1; i >= 0; i--) {
temp = array[0];
array[0] = array[i];
array[i] = temp;
heapSize--;
heapify(array, 0, comp);
}
}
private static void buildHeap(int[] array, Comparator comp) {
heapSize = array.length;
for (int i = (int) Math.floor((array.length) / 2) - 1; i >= 0; i--) {
heapify(array, i, comp);
}
}
private static void heapify(int[] array, int i, Comparator comp) {
left = getLeft(i);
right = getRight(i);
node = ((left <= heapSize - 1) && (comp.compare(array[left], array[i]) > 0))
? left
: i;
if ((right <= heapSize - 1) && (comp.compare(array[right], array[node]) > 0)) {
node = right;
}
if (node != i) {
int temp = array[i];
array[i] = array[node];
array[node] = temp;
heapify(array, node, comp);
}
}
private static int getLeft(int i) {
return (i * 2);
}
private static int getRight(int i) {
return (i * 2 + 1);
}
private static int getParent(int i) {
return (int) Math.floor((i / 2)) - 1;
}
}
public class Lesser implements Comparator<Integer> {
@Override
public int compare(Integer i, Integer j) {
return (i < j)
? 1
: -1;
}
}
public class Greater implements Comparator<Integer> {
@Override
public int compare(Integer i, Integer j) {
return (i > j)
? 1
: -1;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment