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[]){These algorithms were derived from "Introduction to Algorithms by T Cormen, C Leiserson, R Rivest, and C Stein"
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);
}
}
Have fun :)
No comments:
Post a Comment