【啊哈！算法】算法11：堆——神奇的优先队列（上）

以小顶堆为例，（小顶堆一般用来实现降序排列）讲一下堆排序的思路：

1.构建小顶堆
2.将堆顶元素和最后一个元素交换
3.将最后一个元素踢出数组（此时最后一个元素是刚交换下来的最小值）
4.重复前三部，直到数组为空。

时间复杂度：O(N*logN)
不稳定排序

package sort;

//堆排序，以小顶堆为例
public class HeapSort {

    public static void main(String[] args) {
        int[] arr = { 23, 2, 5, 12, 7, 17, 25, 19, 36, 99, 22, 28, 46, 92 };
        int[] arr1 = { 2, 7, 5, 12, 22, 17, 25, 19, 36, 99, 23, 28, 46, 92, 3 };
        // siftdown(0, arr);
        // siftup(arr1.length - 1, arr1);
        heapsort(arr1);
        for (int i : arr1) {
            System.out.println(i);
        }
    }

    // 小顶堆为例
    static void heapsort(int[] array) {
        int len = array.length;
        // 2.交换，踢出最小数
        for (int i = 0; i < len; i++) {
            buildHeap(array, len - i);
            int temp = array[0];
            array[0] = array[array.length - 1 - i];
            array[array.length - 1 - i] = temp;
        }
    }

    // 建堆过程
    static void buildHeap(int[] array, int size) {

        // int len = array.length;
        // 从数组最后一个元素开始
        for (int i = size - 1; i >= 0; i--) {
            siftup(i, array);
        }
    }

    // 向上调整
    static void siftup(int i, int[] arr) {
        int flag = 0;
        while ((i - 1) / 2 >= 0 && 0 == flag) {

            if (arr[i] < arr[(i - 1) / 2]) {
                swap(arr, i, (i - 1) / 2);

            } else {
                flag = 1;
            }
            // 这里可以放到if里,一样的
            i = (i - 1) / 2;
        }

    }

    // 向下调整
    static void siftdown(int i, int[] arr) {
        int len = arr.length;
        int flag = 0;
        int index = i;
        while (2 * i + 1 <= len - 1 && flag == 0) {
            // 与左孩子比较
            if (arr[i] > arr[2 * i + 1]) {
                index = 2 * i + 1;
            } else {
                index = i;
            }

            // 与右孩子比较
            if (2 * i + 2 <= len - 1) {
                if (arr[index] > arr[2 * i + 2]) {
                    index = 2 * i + 2;
                }
            }
            
            if (index != i) {
                swap(arr, i, index);
                i = index;
            } else {
                flag = 1;
            }
        }

    }

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