HeapSort

public class HeapSort {  
	
	public static void main(String[] args) {
		Integer[] datas = {5,1,56,4,9,7,23,108,34,24,12};
		sort(datas);
	}
	  
    public static void sort(Integer[] datas) {  
        // 构建最大堆  
        buildMaxHeap(datas);  
        // 循环，每次把根节点和最后一个节点调换位置  
        for (int i = datas.length; i > 1; i--) {  
            Integer tmp = datas[0];  
            datas[0] = datas[i - 1];  
            datas[i - 1] = tmp;  

            for(Integer data : datas) {
    			System.out.print(data + "\t");
    		}
            System.out.println();
            // 堆的长度减少1，排除置换到最后位置的根节点  
            maxHeapify(datas, 1, i - 1);  
        }  
    }  

    // 根据输入数组构建一个最大堆  
    private static void buildMaxHeap(Integer[] data) {  
    	// 其中有一般是叶子节点，不需要全部进行构建
        for (int i = data.length / 2; i > 0; i--) {  
            maxHeapify(data, i, data.length);  
        }  
    }  

    //堆调整，使其生成最大堆  
    private static void maxHeapify(Integer[] data, int parentNodeIndex, int heapSize) {  
        // 计算左节点索引
        int leftChildNodeIndex = parentNodeIndex * 2;  
        // 计算右节点索引  
        int rightChildNodeIndex = parentNodeIndex * 2 + 1;  
        // 最大节点索引  
        int largestNodeIndex = parentNodeIndex;  

        // 如果左节点存在并且左子节点大于父节点，则将左子节点作为最大节点  
        if (leftChildNodeIndex <= heapSize && data[leftChildNodeIndex - 1] > data[parentNodeIndex - 1]) {  
            largestNodeIndex = leftChildNodeIndex;  
        }  

        // 如果有节点存在并且右子节点比最大节点还大，那么最大节点应该是右子节点  
        if (rightChildNodeIndex <= heapSize && data[rightChildNodeIndex - 1] > data[largestNodeIndex - 1]) {  
            largestNodeIndex = rightChildNodeIndex;  
        }  

        // 最后，如果最大节点和父节点不一致，则交换他们的值  
        if (largestNodeIndex != parentNodeIndex) {  
            Integer tmp = data[parentNodeIndex - 1];  
            data[parentNodeIndex - 1] = data[largestNodeIndex - 1];  
            data[largestNodeIndex - 1] = tmp;  

            // 交换完父节点和子节点的值，对换了值的子节点检查是否符合最大堆的特性  
            maxHeapify(data, largestNodeIndex, heapSize);  
        }  
    }  
}