public class HeapSort {
	public static void main(String[] args) {
		int[] array = new int[] { 2, 1, 4, 3, 6, 5, 8, 7 };
		// 接下來就是排序的主體邏輯
		sort(array);
		System.out.println(Arrays.toString(array));
	}
	/**
	 * 
	 * @description 本方法只有一個(gè)參數(shù)，那就是待排序的array
	 * @author
	 * @param
	 * @return
	 * @time 2018年3月9日 下午2:24:45
	 */
	public static void sort(int[] array) {
		// 按照完全二叉樹的特點(diǎn)，從最后一個(gè)非葉子節(jié)點(diǎn)開始，對(duì)于整棵樹進(jìn)行大根堆的調(diào)整
		// 也就是說，是按照自下而上，每一層都是自右向左來進(jìn)行調(diào)整的
		// 注意，這里元素的索引是從0開始的
		// 另一件需要注意的事情，這里的建堆，是用堆調(diào)整的方式來做的
		// 堆調(diào)整的邏輯在建堆和后續(xù)排序過程中復(fù)用的
		for (int i = array.length / 2 - 1; i >= 0; i--) {
			adjustHeap(array, i, array.length);
		}
		// 上述邏輯，建堆結(jié)束
		// 下面，開始排序邏輯
		for (int j = array.length - 1; j > 0; j--) {
			// 元素交換
			// 說是交換，其實(shí)質(zhì)就是把大頂堆的根元素，放到數(shù)組的最后；換句話說，就是每一次的堆調(diào)整之后，都會(huì)有一個(gè)元素到達(dá)自己的最終位置
			swap(array, 0, j);
			// 元素交換之后，毫無疑問，最后一個(gè)元素?zé)o需再考慮排序問題了。
			// 接下來我們需要排序的，就是已經(jīng)去掉了部分元素的堆了，這也是為什么此方法放在循環(huán)里的原因
			// 而這里，實(shí)質(zhì)上是自上而下，自左向右進(jìn)行調(diào)整的
			adjustHeap(array, 0, j);
		}
	}
	/**
	 * 
	 * @description 這里，是整個(gè)堆排序最關(guān)鍵的地方，正是因?yàn)榘堰@個(gè)方法抽取出來，才更好理解了堆排序的精髓，會(huì)盡可能仔細(xì)講解
	 * @author
	 * @param
	 * @return
	 * @time 2018年3月9日 下午2:54:38
	 */
	public static void adjustHeap(int[] array, int i, int length) {
		// 先把當(dāng)前元素取出來，因?yàn)楫?dāng)前元素可能要一直移動(dòng)
		int temp = array[i];
		// 可以參照sort中的調(diào)用邏輯，在堆建成，且完成第一次交換之后，實(shí)質(zhì)上i=0；也就是說，是從根所在的最小子樹開始調(diào)整的
		// 接下來的講解，都是按照i的初始值為0來講述的
		// 這一段很好理解，如果i=0；則k=1；k+1=2
		// 實(shí)質(zhì)上，就是根節(jié)點(diǎn)和其左右子節(jié)點(diǎn)記性比較，讓k指向這個(gè)不超過三個(gè)節(jié)點(diǎn)的子樹中最大的值
		// 這里，必須要說下為什么k值是跳躍性的。
		// 首先，舉個(gè)例子，如果a[0] > a[1]&&a[0]>a[2],說明0,1,2這棵樹不需要調(diào)整，那么，下一步該到哪個(gè)節(jié)點(diǎn)了呢？肯定是a[1]所在的子樹了，
		// 也就是說，是以本節(jié)點(diǎn)的左子節(jié)點(diǎn)為根的那棵小的子樹
		// 而如果a[0}<a[2]呢，那就調(diào)整a[0]和a[2]的位置，然后繼續(xù)調(diào)整以a[2]為根節(jié)點(diǎn)的那棵子樹，而且肯定是從左子樹開始調(diào)整的
		// 所以，這里面的用意就在于，自上而下，自左向右一點(diǎn)點(diǎn)調(diào)整整棵樹的部分，直到每一顆小子樹都滿足大根堆的規(guī)律為止
		for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
			// 讓k先指向子節(jié)點(diǎn)中最大的節(jié)點(diǎn)
			if (k + 1 < length && array[k] < array[k + 1]) {
				k++;
			}
			// 如果發(fā)現(xiàn)子節(jié)點(diǎn)更大，則進(jìn)行值的交換
			if (array[k] > temp) {
				swap(array, i, k);
				// 下面就是非常關(guān)鍵的一步了
				// 如果子節(jié)點(diǎn)更換了，那么，以子節(jié)點(diǎn)為根的子樹會(huì)不會(huì)受到影響呢？
				// 所以，循環(huán)對(duì)子節(jié)點(diǎn)所在的樹繼續(xù)進(jìn)行判斷
				i = k;
				// 如果不用交換，那么，就直接終止循環(huán)了
			} else {
				break;
			}
		}
	}
	/**
	 * 交換元素
	 * 
	 * @param arr
	 * @param a
	 *            元素的下標(biāo)
	 * @param b
	 *            元素的下標(biāo)
	 */
	public static void swap(int[] arr, int a, int b) {
		int temp = arr[a];
		arr[a] = arr[b];
		arr[b] = temp;
	}
}

/**
 * @Author: 白雄雄
 * @Date: 2019/9/10 13:48
 */
public class SmailHeap {
    public static void main(String[] args) {
        int[] array = new int[]{1,3,2,7,4,0,5,10};
        heapSort(array);
        System.out.println(Arrays.toString(array));
    }
    private static void heapSort(int[] array) {
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            adjustHeap(array,i,array.length);
        }
        for (int j = array.length - 1; j >= 0; j--) {
            int temp = array[0];
            array[0] = array[j];
            array[j] = temp;
            adjustHeap(array,0,j);
        }
    }
    private static void adjustHeap(int[] array, int i, int len) {
        int temp = array[i];
        for (int k = i * 2 + 1; i < len; k = 2 * k + 1) {
            if (k + 1 < len && array[k] > array[k + 1]) {
                k++;
            }
            if (k<len && array[k] < temp) {
                array[i] = array[k];
                i = k;
            } else {
                break;
            }
        }
        array[i] = temp;
    }
}