// , ( ),
// ,
class HeapSort2 {
public static void main(String[] args)
{
int[] heap=createHeap(new int[]{5, 2, 7, 3, 6, 1, 4, 6});
sort(heap,0);
println(heap);
}
private static void println(int[] arr)
{
for (int i : arr) {
System.out.print(" "+i);
}
System.out.println();
}
private static int[] createHeap(int[] randomArray)
{
int[] heap=new int[randomArray.length];
for(int index=0;index0)
{
parentIndex=(lastIndex-1)/2;
int parentValue=src[parentIndex];
//
if(element>parentValue)
{
src[parentIndex]=element;
src[currentIndex]=parentValue;
currentIndex=parentIndex;
}else break;
}
}
private static void sort(int [] src,int poppedCount)
{
if (poppedCount lastIndex)
break;
int childIndexRight = currentIndex * 2 + 2;
int childLeftValue = src[childIndexLeft];
int desChildIndex=childIndexLeft;
int desChildValue =childLeftValue;
if (childIndexRight <= lastIndex)
{
int childRightValue = src[childIndexRight];
if(childLeftValue < childRightValue)
{
desChildIndex =childIndexRight;
desChildValue =childRightValue;
}
}
int parentValue = src[currentIndex];
//
if (parentValue != Math.max(parentValue, desChildValue)) {
src[desChildIndex] = parentValue;
src[currentIndex] = desChildValue;
currentIndex = desChildIndex;
} else break;
}
sort(src,poppedCount);
}
}
}