package com.luna.sort;
public class HeapSortMaxAndMin{
	public static void main(String[] args) {
		int[] array = { 19, 38, 7, 36, 5, 5, 3, 2, 1, 0, 56 };
		System.out.println("排序前:");
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i] + ",");
		}
		System.out.println();
		System.out.println("分割線---------------");
		heapSort(array);
		System.out.println("排序后:");
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i] + ",");
		}
	}
	public static void heapSort(int[] array) {
		if (array == null || array.length == 1)
			return;
		buildArrayToHeap(array); //將數(shù)組元素轉(zhuǎn)化為大頂堆/小頂堆
		for (int i = array.length - 1; i >= 1; i--) {
			// 經(jīng)過(guò)上面的一些列操作，目前array[0]是當(dāng)前數(shù)組里最大的元素，需要和末尾的元素交換，然后拿出最大的元素
			swap(array, 0, i);
			/**
			 * 交換完后，下次遍歷的時(shí)候，就應(yīng)該跳過(guò)最后一個(gè)元素，也就是最大的那個(gè)
			 * 值，然后開(kāi)始重新構(gòu)建最大堆堆的大小就減去1，然后從0的位置開(kāi)始最大堆
			 */
//			buildMaxHeap(array, i, 0);
			buildMinHeap(array, i, 0);
		}
	}
	// 構(gòu)建堆
	public static void buildArrayToHeap(int[] array) {
		if (array == null || array.length == 1)
			return;
		//遞推公式就是 int root = 2*i, int left = 2*i+1, int right = 2*i+2;
		int cursor = array.length / 2;
		for (int i = cursor; i >= 0; i--) { // 這樣for循環(huán)下，就可以第一次排序完成
//			buildMaxHeap(array, array.length, i);
			buildMinHeap(array, array.length, i);
		}
	}
	//大頂堆
	public static void buildMaxHeap(int[] array, int heapSieze, int index) {
		int left = index * 2 + 1; // 左子節(jié)點(diǎn)
		int right = index * 2 + 2; // 右子節(jié)點(diǎn)
		int maxValue = index; // 暫時(shí)定在Index的位置就是最大值
		// 如果左子節(jié)點(diǎn)的值，比當(dāng)前最大的值大，就把最大值的位置換成左子節(jié)點(diǎn)的位置
		if (left < heapSieze && array[left] > array[maxValue]) {
			maxValue = left;
		}
		// 如果右子節(jié)點(diǎn)的值，比當(dāng)前最大的值大，就把最大值的位置換成右子節(jié)點(diǎn)的位置
		if (right < heapSieze && array[right] > array[maxValue]) {
			maxValue = right;
		}
		// 如果不相等說(shuō)明，這個(gè)子節(jié)點(diǎn)的值有比自己大的，位置發(fā)生了交換了位置
		if (maxValue != index) {
			swap(array, index, maxValue); // 就要交換位置元素
			// 交換完位置后還需要判斷子節(jié)點(diǎn)是否打破了最大堆的性質(zhì)。最大堆性質(zhì)：兩個(gè)子節(jié)點(diǎn)都比父節(jié)點(diǎn)小。
			buildMaxHeap(array, heapSieze, maxValue);
		}
	}
	//小頂堆
	public static void buildMinHeap(int[] array, int heapSieze, int index) {
		int left = index * 2 + 1; // 左子節(jié)點(diǎn)
		int right = index * 2 + 2; // 右子節(jié)點(diǎn)
		int maxValue = index; // 暫時(shí)定在Index的位置就是最小值
		// 如果左子節(jié)點(diǎn)的值，比當(dāng)前最小的值小，就把最小值的位置換成左子節(jié)點(diǎn)的位置
		if (left < heapSieze && array[left] < array[maxValue]) {
			maxValue = left;
		}
		// 如果右子節(jié)點(diǎn)的值，比當(dāng)前最小的值小，就把最小值的位置換成左子節(jié)點(diǎn)的位置
		if (right < heapSieze && array[right] < array[maxValue]) {
			maxValue = right;
		}
		// 如果不相等說(shuō)明這個(gè)子節(jié)點(diǎn)的值有比自己小的，位置發(fā)生了交換了位置
		if (maxValue != index) {
			swap(array, index, maxValue); // 就要交換位置元素
			// 交換完位置后還需要判斷子節(jié)點(diǎn)是否打破了最小堆的性質(zhì)。最小性質(zhì)：兩個(gè)子節(jié)點(diǎn)都比父節(jié)點(diǎn)大。
			buildMinHeap(array, heapSieze, maxValue);
		}
	}
	// 數(shù)組元素交換
	public static void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}

import java.util.Arrays;
public class MaxHeapSort {
    private int[] arr;
    public MaxHeapSort(int[] arr){
        this.arr = arr;
    }
    /**
     * 堆排序的主要入口方法，共兩步。
     */
    public void sort(){
        /*
         *  第一步：將數(shù)組堆化
         *  beginIndex = 第一個(gè)非葉子節(jié)點(diǎn)。
         *  從第一個(gè)非葉子節(jié)點(diǎn)開(kāi)始即可。無(wú)需從最后一個(gè)葉子節(jié)點(diǎn)開(kāi)始。
         *  葉子節(jié)點(diǎn)可以看作已符合堆要求的節(jié)點(diǎn)，根節(jié)點(diǎn)就是它自己且自己以下值為最大。
         */
        int len = arr.length - 1;
        int beginIndex = (len - 1) >> 1; 
        for(int i = beginIndex; i >= 0; i--){
            maxHeapify(i, len);
        }
        /*
         * 第二步：對(duì)堆化數(shù)據(jù)排序
         * 每次都是移出最頂層的根節(jié)點(diǎn)A[0]，與最尾部節(jié)點(diǎn)位置調(diào)換，同時(shí)遍歷長(zhǎng)度 - 1。
         * 然后從新整理被換到根節(jié)點(diǎn)的末尾元素，使其符合堆的特性。
         * 直至未排序的堆長(zhǎng)度為 0。
         */
        for(int i = len; i > 0; i--){
            swap(0, i);
            maxHeapify(0, i - 1);
        }
    }
    private void swap(int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    /**
     * 調(diào)整索引為 index 處的數(shù)據(jù)，使其符合堆的特性。
     * @param index 需要堆化處理的數(shù)據(jù)的索引
     * @param len 未排序的堆（數(shù)組）的長(zhǎng)度
     */
    private void maxHeapify(int index,int len){
        int li = (index << 1) + 1; // 左子節(jié)點(diǎn)索引
        int ri = li + 1;           // 右子節(jié)點(diǎn)索引
        int cMax = li;             // 子節(jié)點(diǎn)值最大索引，默認(rèn)左子節(jié)點(diǎn)。
        if(li > len) return;       // 左子節(jié)點(diǎn)索引超出計(jì)算范圍，直接返回。
        if(ri <= len && arr[ri] > arr[li]) // 先判斷左右子節(jié)點(diǎn)，哪個(gè)較大。
            cMax = ri;
        if(arr[cMax] > arr[index]){
            swap(cMax, index);      // 如果父節(jié)點(diǎn)被子節(jié)點(diǎn)調(diào)換，
            maxHeapify(cMax, len);  // 則需要繼續(xù)判斷換下后的父節(jié)點(diǎn)是否符合堆的特性。
        }
    }
    /**
     * 測(cè)試用例
     * 輸出：
     * [0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 7, 7, 7, 8, 8, 8, 9, 9, 9]
     */
    public static void main(String[] args) {
        int[] arr = new int[]{3,5,3,0,8,6,1,5,8,6,2,4,9,4,7,0,1,8,9,7,3,1,2,5,9,7,4,0,2,6};        
        new MaxHeapSort(arr).sort();        
        System.out.println(Arrays.toString(arr));
    }
}