I was challenged by a friend to write Heap Sort algo in Java as explained in wikipedia's article.
Here's a slight variant to that along with the test data.
public class TestAlgos{
public static void main(String args[]){
TestAlgos t = new TestAlgos();
int[] testArr = new int[]{45,38,12,62,42,34,8,24,76,48};
t.heapSort(testArr,0,testArr.length); }
public void printArray(int[] a){ System.out.print("arr:{");
for(int i=0; i < a.length; i++){
if(i != 0)
System.out.print(",");
System.out.print(a[i]);
}
System.out.println("}");
}
private void swap(int[] a,int i, int j){
int temp=a[i];a[i]=a[j];a[j]=temp;
}
private void heapSort(int[] arr, int low, int high){
heapify(arr,arr.length);
for(int pos = arr.length-1; pos > 0;pos--){
swap(arr,pos,0);
heapify(arr,pos);
}
System.out.print("Sorted Array:");printArray(arr);
}
private void heapify(int[] arr,int last){
for(int curr = 0; curr < last; curr++){
int parent = getParent(curr);
moveUp(arr,curr,parent);
}
System.out.print("Heapified Array:");printArray(arr);
}
private int getParent(int current){
return (int)((current - 1)/2);
}
private void moveUp(int[] arr,int current, int parent){
if(current == parent || current == 0)
return;
if(arr[current] > arr[parent]){
swap(arr,current,parent);
moveUp(arr,parent,getParent(parent));
}
}
}
No comments:
Post a Comment