Heap Sort in Java

HeapSort.java

import java.util.Arrays;

public class HeapSort {


    public HeapSort() {
    }

    public static void heapSort(int[] arr) {

        int n = arr.length-1;

        for (int i = n/2 ; i >=1 ; i--) {

            reheap( arr,i, n);

        }

        swap(arr,1,n);


        for (int i = 1; i <=  arr.length- 2; i++) {  // 对剩余的元素，还要进行  arr.length -2 次建堆

            reheap(arr, 1, arr.length-1-i);
            swap(arr,1,arr.length-1-i);
        }







    }


    private static void swap(int[] arr, int rootIndex, int lastLeafIndex) {

        int temp = arr[rootIndex];

        arr[rootIndex] =  arr[lastLeafIndex];

        arr[lastLeafIndex] = temp;


        System.out.println("swap:"+ Arrays.toString(arr));

    }


    /**
     * @param childRootIndex 该子树的根节点的索引
     * @param leafIndex      该子树的叶子节点的索引
     */
    public static void reheap(int[] arr, int childRootIndex, int leafIndex) {


        System.out.printf("childRootIndex:"+ childRootIndex);
        int leftChildIndex = 2 * childRootIndex;


        while (leftChildIndex <= leafIndex) {
            int rootValue = arr[childRootIndex]; //根节点的值

            int minValue = 0 ;
            int minIndex = 0;

            int tempValue = 0;

            if (arr[leftChildIndex] < rootValue) {


                minValue = arr[leftChildIndex];
                minIndex = leftChildIndex;


            }else {
                minValue = rootValue;

                minIndex = childRootIndex;

            }

            //我们要从上往下进行建堆，但是到底是对左子树 还是右子树 进行建堆，这需要根据 左孩子 和右孩子的大小来判断，哪个小，就对谁建堆
            if (leftChildIndex + 1 <= leafIndex && arr[leftChildIndex + 1] < minValue) {
                tempValue = arr[childRootIndex];
                arr[childRootIndex] = arr[leftChildIndex + 1];

                arr[leftChildIndex + 1] = tempValue;

                childRootIndex = 2 * childRootIndex +1;  // 继续对右子树进行 建堆操作
            }else {



                tempValue = arr[childRootIndex];
                arr[childRootIndex] = arr[minIndex];

                arr[minIndex] = tempValue;

                childRootIndex = 2 * childRootIndex ;  // 继续对左子树进行 建堆操作
            }





            leftChildIndex = 2 * childRootIndex;


        }


        System.out.println(Arrays.toString(arr));


    }


    public static void main(String[] args) {

//        这里为了方便，以索引1开始。则对于完全二叉树的性质，子树的根节点索引为i，则它的左孩子索引为2*i , 右孩子为 2*i+1（也可以等于“左孩子索引+1）;
//        如果是以索引0开始，则对于完全二叉树的性质，子树的根节点索引为i，则它的左孩子索引为2*i+1 ,右孩子索引为 2*i+2（也可以等于“左孩子索引+1）
        int[] arr = {0,5,3,7,4,6,8,2,1};

        System.out.println("source:"+ Arrays.toString(arr));
        heapSort(arr);


        System.out.println("result:"+Arrays.toString(arr));

    }
}