/**
 * @(#) HeapSort.java Apr 6, 2010 10:07:04 PM
 * Copyright (C) 2009 GeeYee Inc. 60606, Chicago, IL, USA
 * All right reserved
 */
package array;

import java.util.Arrays;

/**
 * Class <code>HeapSort</code>
 *
 * @author Xiaowen dingxwsimon@gmail.com
 * @since Apr 6, 2010 10:07:04 PM
 *
 */
public class HeapSort {
    // max heap
    // only sift the data[low] to the right place
    public static void sift(int[] data, int low, int high) {
        int i, j;
        i = low; // low is the parent
        j = 2 * i + 1; // j is the child
        while (j < high) {
            // decide left or right child
            if (j + 1 < high && data[j] < data[j + 1])
                j = j + 1;
            // if the child if larger than parent, swap
            if (data[i] < data[j]) {
                swap(data, i, j);
                i = j;
                j = 2 * i + 1;
            } else
                break;
        }
    }

    public static void heapsort(int[] data) {
        int length = data.length;
        for (int i = length / 2 - 1; i >= 0; i--) {
            sift(data, i, length - 1);
        }

        for (int i = length - 1; i >= 1; i--) {
            swap(data, 0, i);
            sift(data, 0, i - 1);
        }
    }

    public static void swap(int[] data, int i, int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] data = {2, 13, 1, 12, 11, 7, 9, 10, 20, 6};
        HeapSort.heapsort(data);
        System.out.println(Arrays.toString(data));

    }

}
