class HeapSortDescendingOrder {
private static Comparable[] array;
private static int count;
private HeapSortDescendingOrder() {
}
public static void sort(Comparable[] list) {
// assign list to array so it can be used in private methods without passing to method parameter
array = list;
count = list.length;
// Build min heap
for(int i = array.length/2; i >= 0; i--) {
sink(i);
}
// shift each element at sorted position
while(count > 0) {
// put 0th element in it's sorted positon
swap(0, --count);
// maintain heap property
sink(0);
}
}
private static void sink(int root) {
int child = getLeftChildIndex(root);
while(child <= count-1) {
// if there is right child. Right chlild = Left child + 1
if(child < count-1 && greater(array[child], array[child+1])) {
child = child + 1;// point child to right child as it is lesser than left child
}
// if binary heap property already satisfied then break the loop
if(greater(array[child], array[root])) {
break;
}
swap(root, child);
root = child;
child = getLeftChildIndex(root);
}
}
private static boolean greater(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;
}
/**
* Get parent index of binary heap node. Index start with 0.
*/
private static int getParentIndex(int i) {
return (i-1)/2;
}
/**
* Get left child index of binary heap node. Index start with 0.
*/
private static int getLeftChildIndex(int i) {
return (2*i+1);
}
/**
* Get left child index of binary heap node. Index start with 0.
*/
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};
HeapSortDescendingOrder.sort(arrayInts);
// Print sorted elements
display();
System.out.println("\nTest 2 ");
String[] arrayStr = new String[] {"My", "Name", "Is", "Raghav", "M", "And", "I", "Stay", "In", "Bangalore"};
HeapSortDescendingOrder.sort(arrayStr);
// Print sorted elements
display();
}
}
Test 1
24 16 13 12 11 10 9 7 5 3
Test 2
Stay Raghav Name My M Is In I Bangalore And
Comments
Post a Comment