Tuesday, April 5, 2016

Heap Sort Utility for Generic classes

In below I have written one simple Heap Utility class for sorting any kind of comparable objects.

Comparable objects means object of class which inherit the java.lang.Comaparable class.
As for example Integer, Long, String etc.

Here is the code snippet of the utility class.

<SNIP>
/**
 * This utility class is for implementation
 * of HeapSort for any type of comparable objects
 * @author Iftikar
 *
 * @param <T>
 */
class HeapUtilTemplate<T extends Comparable<T>> {
T[] A;
int heapSize;

public HeapUtilTemplate(T[] arr1) {
this.A = arr1;
this.heapSize = arr1.length;
}
/**
* Method to sort the array using heapSort
*/
public void heapSort(){
//displayArr();
buildMaxHeap();
//displayArr();
for(int i=heapSize-1;i>0;i--){
T temp=A[i];
A[i]=A[0];
A[0]=temp;
heapSize=heapSize-1;
maxHeapify(A, 0);
}
}

public void displayArr(){

for(T i:A){
System.out.print(i+" ");
}
System.out.println();
}


/**
* Method to build the max heap
*/
public void buildMaxHeap(){

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


/**
* Method to Heapify(max) the array
* @param A
* @param i
*/
public void maxHeapify(T[] A, int i){
int l=left(i);
int r=right(i);
int largest=i;
if(l<heapSize && A[i].compareTo(A[l]) < 0){//A[i] < A[l]
largest=l;
}
if(r<heapSize && A[r].compareTo(A[largest])>0){//A[r]>A[largest]
largest=r;
}
if(largest!=i){
//exchange data
T temp=A[i];
A[i]=A[largest];
A[largest]=temp;
maxHeapify(A,largest);
}
}
public int parent(int i){
return i/2;
}

public int left(int i){
return 2*i+1;
}

public int right(int i){
return 2*i+2;
}
}
</SNIP>

Please comment below if the code can be made better. Your inputs are always welcome.





No comments:

Post a Comment