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;
}
}
// 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