Wednesday, January 5, 2011

Heap Sort Algorithms with Java

It's my homework before new year.
Well not much to talk today. Let's have a look.
//*************Find Left and Right****************//
public static int left(int i){
          return (2*i)+1;
}
public static int right(int i){
          return (2*i)+2;
}
//************Max Heapify**********************//
public static void max_heapify(int x[],int i){
int l = left(i);
int r = right(i);
int largest;
     if(l<=(heap_size) && x[l] > x[i]){
          largest = l;
     }
     else
          largest = i;
     if(r<=(heap_size) && x[r] > x[largest]){
          largest = r;
     }
     if(largest != i){
          //SWAP
          int temp = x[i];
          x[i] = x[largest];
          x[largest] = temp;
          max_heapify(x,largest);
     }
}
public static void build_max_heap(int x[]){
     for(int i = (x.length/2)-1;i>=0;i--){
          max_heapify(x,i);
     }
}
public static void heap_sort(int x[]){
     build_max_heap(x);
     int temp;
     heap_size = x.length-1;
          for(int i = heap_size;i>=0;i--){
               temp = x[0];
               x[0] = x[i];
               x[i] = temp;
               heap_size--;
               max_heapify(x,0);


         }
}
These algorithms were derived from "Introduction to Algorithms by T Cormen, C Leiserson, R Rivest, and C Stein"

Have fun :)

No comments:

Post a Comment