ヒープソート(2)


//     ,       (   ),      
//             ,                

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

    }

}