HEAP SORT IMPLEMENTATION IN JAVA

Following is my Heap Sort implementation in Java. It's very easy and provides a level zero insight into how you can easily implement your algorithms . Following contains code for both max and min heap implementations.


public static void main(String[] args) {
int[] ar = gyle.random.RandomArray.generateRandromArray(10000);

heapSort(ar);

for (int i = 0; i < ar.length; i++) {
System.out.print(ar[i] + " ");
}

}

public static int[] heapSort(int[] ar) {
buildMaxheap(ar);

/**
* Now Sorting the array.
*/
int changingSize = ar.length;
while (changingSize > 1) {
/**
* topmost element is the largest so put it in the last position
*/
int temp = ar[changingSize - 1];
ar[changingSize - 1] = ar[0];
ar[0] = temp;
/**
* again maintain the heap property properly throughout the heap
* starting at the exchanged position .
*/
changingSize = changingSize - 1; or --changingSize
maxHeapify(ar, 0, changingSize);

}
return ar;
}

public static void buildMaxheap(int[] ar) {

for (int i = ar.length / 2; i >= 0; i--) {
maxHeapify(ar, i, ar.length);
}
}

public static void maxHeapify(int[] ar, int i, int changingSize) {
int largestIndex = i;
int leftChild, rightChild;

if (i != 0) {
leftChild = i * 2;
rightChild = i * 2 + 1;
} else {
/**
* this is an extra thing from the algo -> as when u will have a 0th
* index element the left child would end up being the 0th element
* if you use 2* i so you need to specify it explicitly
*/
leftChild = 1;
rightChild = 2;
}
if (leftChild <= changingSize - 1 && ar[leftChild] > ar[i]) {
largestIndex = leftChild;
}
if (rightChild <= changingSize - 1 && ar[rightChild] > ar[largestIndex]) {
largestIndex = rightChild;
}
if (largestIndex != i) {
/**
* swapping without creating a temporary space in memory
*/

ar[i] = ar[largestIndex] - ar[i];
ar[largestIndex] = ar[largestIndex] - ar[i];
ar[i] = ar[largestIndex] + ar[i];
/**
* maintaining the heap property.
*/
maxHeapify(ar, largestIndex, changingSize);
}


public static void buildMinheap(int[] ar) {

for (int i = ar.length / 2; i >= 0; i--) {
minHeapify(ar, i, ar.length);
}
}

public static void minHeapify(int[] ar, int i, int changingSize) {
int smallestIndex = i;
int leftChild, rightChild;

if (i != 0) {
leftChild = i * 2;
rightChild = i * 2 + 1;
} else {
/**
* this is an extra thing from the algo -> as when u will have a 0th
* index element the left child would end up being the 0th element
* if you use 2* i so you need to specify it explicitly
*/
leftChild = 1;
rightChild = 2;
}
if (leftChild <= changingSize - 1 && ar[leftChild] < ar[i]) {
smallestIndex = leftChild;
}
if (rightChild <= changingSize - 1
&& ar[rightChild] < ar[smallestIndex]) {
smallestIndex = rightChild;
}
if (smallestIndex != i) {
/**
* swapping without creating a temporary space in memory
*/

int temp = ar[i] ;
ar[i] = ar[smallestIndex] ;
ar[smallestIndex] = temp;
System.out.println("Done ---> Heapify");
/**
* maintaining the heap property.
*/
minHeapify(ar, smallestIndex, changingSize);
}

}


}