Wednesday, August 31, 2011

Heap Sort

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: