堆排序

很久以前有人问我大数据取n个最大数或者最小数用什么方法最效率，开始我没想到，后面想到了堆排序。
在介绍堆排序之前，首先需要说明一下，堆是个什么玩意儿。

堆是一棵顺序存储的完全二叉树，出于简便起见,完全二叉树通常采用数组而不是链表存储,其存储结构如下:
int[] array = new int[] { 0,1,2,3..n-1 };长度为n
对于tree[i]，有如下特点：
第i个节点的如果有左孩子节点为 2i+1，如果有右孩子为2i+2

在完全二叉树的基础上，如果中每个结点都不大于其子结点，这样的堆称为小顶堆。每个结点的都不小于其子结点，这样的堆称为大顶堆。
那么取n个极值的问题通过堆排序可以转换成大顶堆或者小顶堆n次移除根节点再重新规划的过程。

现在对于堆排序来说，就是把待排序的一堆无序的数，整理成一个大顶堆，或者小顶堆。

其基本思想为(大顶堆)：
1.将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无须区；
2.将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R[1,2...n-1]<=R[n];
3.由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

'''
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));
}

public static void sort(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--) {
        // 每次找到最大的也就是数组的第0个对象与当前进入排序区的数组末尾对象交换，然后重新排序，完成后j减1，不断递归
        swap(array, 0, j);
        adjustHeap(array, 0, j);
    }
}


public static void adjustHeap(int[] array, int i, int length) {
    int temp = array[i];

    for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
        // 让k先指向子节点中最大的节点
        if (k + 1 < length && array[k] < array[k + 1]) {
            k++;
        }

        // 如果发现子节点更大，则进行值的交换
        if (array[k] > temp) {
            swap(array, i, k);
            // 如果子节点更换了，那么，以子节点为根的子树会不会受到影响呢？
            // 所以，循环对子节点所在的树继续进行判断否则就直接终止循环了
            i = k;
        } else {
            break;
        }
    }
}


public static void swap(int[] arr, int a, int b) {
    int temp = arr[a];
    arr[a] = arr[b];
    arr[b] = temp;
}

}
'''