class HeapSortAscendingOrder {
private static Comparable[] array;
private static int count;
private HeapSortAscendingOrder() {
}
public static void sort(Comparable[] list) {
array = list;
count = list.length;
for(int i = array.length/2; i >= 0; i--) {
sink(i);
}
while(count > 0) {
swap(0, --count);
sink(0);
}
}
private static void sink(int root) {
int child = getLeftChildIndex(root);
while(child <= count-1) {
if(child < count-1 && less(array[child], array[child+1])) {
child = child + 1;
}
if(less(array[child], array[root])) {
break;
}
swap(root, child);
root = child;
child = getLeftChildIndex(root);
}
}
private static boolean less(Comparable key1, Comparable key2) {
return key1.compareTo(key2) < 0;
}
private static void swap(int i, int j) {
Comparable temp = array[i];
array[i] = array[j];
array[j] = temp;
}
private static int getParentIndex(int i) {
return (i-1)/2;
}
private static int getLeftChildIndex(int i) {
return (2*i+1);
}
private static int getRightChildIndex(int i) {
return (2*i+2);
}
private static void display() {
for(Comparable key : array) {
System.out.print(key + " ");
}
}
public static void main (String[] args) {
System.out.println("Test 1 ");
Integer[] arrayInts = new Integer[] {11,13,7,12,16,9,24,5,10,3};
HeapSortAscendingOrder.sort(arrayInts);
display();
System.out.println("\nTest 2 ");
String[] arrayStr = new String[] {"My", "Name", "Is", "Raghav", "M", "And", "I", "Stay", "In", "Bangalore"};
HeapSortAscendingOrder.sort(arrayStr);
display();
}
}
Test 1
3 5 7 9 10 11 12 13 16 24
Test 2
And Bangalore I In Is M My Name Raghav Stay
Comments
Post a Comment