package com.hzins.suanfa;

import java.util.Arrays;

/**
 * 堆排序
 * 思路，建立最大堆并把最大的数移到最后，从第一行到倒数第二行建立最大堆
 * 建立最大堆：
 * for循环 以lastindex的父节点为起始位，每此循环自减，直到为1
 * 对于每个父节点肯定会有左子树（要不然他就不是父节点了） 判断有没有右字数
 * 拿到这两个位置的最大值，然后与父节点做比较，最大的放在父节点上，依次循环
 * 树顶判断完毕
 * @author Administrator
 *
 */
public class HeapSort {
    public static void heapSort(int[] data){
        for(int i = data.length - 1;i >= 1; i--){
            createMaxHeap(data, i);
            swap(data, i, 0);
            
        }
    }
    /**
     * 参数lastIndex是用来做出父节点的，如果lastIndex为0的话
     * (lastIndex - 1) / 2算出的父节点为负，越界了，所以lastIndex最小为1
     * @param data
     * @param lastIndex
     */
    public static void createMaxHeap(int[] data, int lastIndex){
        for(int i = (lastIndex - 1) / 2; i >= 0; i --){
            //父节点
            int k = i;
            int bigger = k * 2 + 1; // 定义最大为左孩子
            //有rightChildren
            if(k * 2 + 2 <= lastIndex){
                bigger = data[bigger] > data[k * 2 + 2] ? bigger : bigger + 1;
            }
            if(data[k] < data[bigger]){
                swap(data, k, bigger);
            }
        }
    }
    public static void swap(int[] array, int a, int b){
        int temp = array[a];
        array[a] = array[b];
        array[b] = temp;
        
    }
    //start 6, 4, 7, 3, 3, 1, 8
    public static void main(String[] args) {
        int[] array = {6, 4, 7, 3, 3, 1, 8};
        heapSort(array);
//        createMaxHeap(array, 0);
        System.out.println(Arrays.toString(array));
    }
}