HeapSort.javba

import java.util.Arrays;
class HeapSort{
public static void sort(int[] A){
buildMaxHeap(A);
int heapSize = A.length;
for(int i=A.length-1;i>0;i--){
int tmp = A[0];
A[0] = A[i];
A[i] = tmp;
heapSize--;
maxHeapify(A,heapSize,0);
}
}
private static void buildMaxHeap(int[] A){
for(int i=A.length/2-1;i>=0;i--){
maxHeapify(A,A.length,i);
}
}
//i>0 and i<A.length, no check on i
private static void maxHeapify(int[] A,int heapSize,int i){
int l = 2*i+1;
int r = 2*i+2;
int largest = 0;
if(l<=heapSize-1&&A[l]>A[i]){
largest = l;
}
else{
largest = i;
}
if(r<=heapSize-1&&A[r]>A[largest]){
largest = r;
}
if(largest!=i){
int tmp = A[largest];
A[largest] = A[i];
A[i] = tmp;
maxHeapify(A,heapSize,largest);
}
}
}