Friday, September 13, 2013

heap sort optimized code

static void HeapSort(int[] arr) {
// TODO Auto-generated method stub
for(int i=0; i<arr.length;i++)
{
System.out.print(" "+arr[i]);
createHeap(arr,i);
}

System.out.println("     ");
System.out.println("heap generated");
for(int i=0; i<arr.length;i++)
{
System.out.print(" "+arr[i]);
}
for(int last=arr.length-1;last>0;)
{
int temp =arr[0];
arr[0]= arr[last];
arr[last--]=temp;
if(last>0)
fixHeap(arr,last);
}
}



private static void fixHeap(int[] arr,int last)
{
int currentIndex = 0;
boolean isHeap = false;

while (!isHeap) {
int leftChildIndex = 2 * currentIndex + 1;
int rightChildIndex = 2 * currentIndex + 2;
int maxIndex = currentIndex;

if (leftChildIndex <= last &&
arr[maxIndex] < arr[leftChildIndex]) {
maxIndex = leftChildIndex;
}

if (rightChildIndex <= last &&
arr[maxIndex] < arr[rightChildIndex]) {
maxIndex = rightChildIndex;
}

if (maxIndex != currentIndex) {
// Swap list[currentIndex] with list[maxIndex]
int temp = arr[currentIndex];
arr[currentIndex] = arr[maxIndex];
arr[maxIndex] = temp;
currentIndex = maxIndex;
} else {
isHeap = true;
}
}
}

private static void createHeap(int[] arr,int p) {
// TODO Auto-generated method stub
int parent=p;
while(parent> 0 && arr[parent]>arr[(parent-1)/2])
{
int temp=arr[parent];
arr[parent]=arr[(parent-1)/2];
arr[(parent-1)/2]=temp;

parent=(parent-1)/2;

}
}

No comments:

Post a Comment