package sort;

/**
 * Created by ozc on 2018/3/20.
 *
 * @author ozc
 * @version 1.0
 */
public class HeapifySort {

    public static void main(String[] args) {

        int[] arrays = {6, 3, 8, 5,2,-1,-5,-2,-6,345,7, 5, 1, 2, 23, 4321, 432, 3, 2, 34234, 2134, 1234, 5, 132423, 234, 4, 2, 4, 1, 5, 2, 5};

        // ..
        maxHeapify(arrays, arrays.length - 1);
        int size = arrays.length - 1;

        for (int i = 0; i < arrays.length; i++) {
            //
            int temp = arrays[0];
            arrays[0] = arrays[(arrays.length - 1) - i];
            arrays[(arrays.length - 1) - i] = temp;

            // 
            heapify(arrays, 0, size);
            size--;
        }
        System.out.println("Java3y" + arrays);
    }

    /**
     * ()
     */
    public static void maxHeapify(int[] arrays, int size) {
        for (int i = size - 1; i >= 0; i--) {
            heapify(arrays, i, size);
        }
    }

    /**
     * 
     *
     * @param arrays          
     * @param currentRootNode 
     * @param size            
     */
    public static void heapify(int[] arrays, int currentRootNode, int size) {

        if (currentRootNode < size) {
            //
            int left = 2 * currentRootNode + 1;
            int right = 2 * currentRootNode + 2;

            //
            int max = currentRootNode;

            if (left < size) {
                //
                if (arrays[max] < arrays[left]) {
                    max = left;
                }
            }
            if (right < size) {
                //
                if (arrays[max] < arrays[right]) {
                    max = right;
                }
            }
            //
            if (max != currentRootNode) {
                int temp = arrays[max];
                arrays[max] = arrays[currentRootNode];
                arrays[currentRootNode] = temp;

                //
                heapify(arrays, max, size);
            }
        }
    }

}