可以利用堆、外排序的方法来做多个处理单元的结果合并

写在前面：

堆通常是一个可以被看做一棵`完全二叉树的数组对象`，
小根堆，最小值在`arr[0]`；    大根堆，最大值在`arr[0]`
插入节点的时间复杂度是`O(log(n))`,获取最值的时间复杂度是`O(1)`

堆，其实就是一个完全二叉树；
完全二叉树，要么是一个满二叉树，要么叶子节点层为从左到右；
堆，实际中是可以用数组实现的；

规律，把数组脑补成完全二叉树
节点 n 的左孩子为 2*n + 1,也就是 n<<1 +1
节点 n 的左孩子为 2*n + 2,也就是 n<<1 +2
节点 n 的父节点为 (n-1)/2,也就是 (n-1)>>2

堆分为小根堆、大根堆
小根堆：在完全二叉树中，任何一个子树的最小值都在头部，小根堆，数组最小值在arr[0]
大根堆：在完全二叉树中，任何一个子树的最大值都在头部，大根堆，数组最大值在arr[0]

堆排序

思想：1、根据大根堆的特点，先将一个数组构建成为一个大根堆，这样堆顶就是最大的
2、再将堆顶和最后一个数互换，将最大的数放到最后，随即调整维持大根堆
继续互换、调整。

    public void heapSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        // 1、将整个数组构建成为大根堆数组
        for (int i = 1; i < arr.length; i++) {
            maxHeapInsert(arr, i);
        }
        // 2、将大根堆对顶(index为0)的数换到最后去，再heapify调整大根堆
        for (int i = arr.length - 1; i >= 0; i--) {
            swap(arr, 0, i);
            heapify(arr, 0, i - 1);
        }
    }
    /**
     * 在arr尾部新增一个数，继续保持arr是大根堆
     * arr 在 p 之前已经是一个大根堆了，现在加入的 p 的数，需要维持 [a,p]是一个大根堆
     * 实现原理：联想大根堆的特点，插入的数如果比父节点大，则向上交换，一直到小于父节点或者堆顶
     * 下标小于0 的情况考虑到的
     *
     * @param arr 传入的数组
     * @param p   指针，表示即将加入的节点
     */
    private void maxHeapInsert(int[] arr, int p) {
        while (arr[p] > arr[(p - 1) / 2]) {
            swap(arr, p, (p - 1) / 2);
            p = (p - 1) / 2;
        }
    }

    /**
     * 大根堆位于index的数与最后一个数互换之后，调整arr继续保持大根堆
     * 在本例堆排序中，是一直将大根堆的最后一个和第一个互换，也就是将最大的值放到最后
     *
     * @param arr       传入的数组
     * @param index     被改变的数的下标，将一直为0
     * @param lastIndex 大根堆的最后一个index
     */
    private void heapify(int[] arr, int index, int lastIndex) {
        // index的左孩子
        int left = index * 2 + 1;
        while (left <= lastIndex) {
            // 判断是否有右孩子，如果有比较左右孩子的大小，选择较大的一个的indx
            int largerSonIndex = left + 1 <= lastIndex && arr[left + 1] > arr[left] ? left + 1 : left;
            // 如果父节点比孩子节点都大的话，就不用调整了，直接返回
            if (arr[index] >= arr[largerSonIndex]) {
                return;
            }
            // 父节点与较大的孩子交换
            swap(arr, index, largerSonIndex);
            index = largerSonIndex;
            left = index * 2 + 1;
        }
    }

应用：

1、优先级队列

java实现的堆结构、优先级队列，PriorityQueue()
PriorityQueue当size达到了初始的initialCapacity容量后会进行扩容，每次容量加1。

        // 默认小顶堆，默认容量为11
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        // 添加比较器，实现大顶堆
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(11, (i1, i2) -> i2-i1);
        //添加数据
        int []arr={2,3,1,4,2,0,5,7};
        for (int each : arr) {
            minHeap.add(each);
            maxHeap.add(each);
        }
        while(minHeap.size()>0){
            System.out.print(minHeap.poll()+" ");
        }
        System.out.println("\n=====");
        while(maxHeap.size()>0){
            System.out.print(maxHeap.poll()+" ");
        }
0 1 2 2 3 4 5 7 
=====
7 5 4 3 2 2 1 0

2、统计流中的中位数：

1->1
1,2->1.5
1,2,3->2
...
准备一个大根堆，一个小根堆
把小于等于大根堆对顶的树插入大根堆，
把大于大根堆对顶的树插入小根堆；
同时，要调整大根堆和小根堆的数量，数量差值不要超过1；
如果大根堆的size大了，就把大根堆 的堆顶取出插入小根堆；
如果小根堆的size大了，就把小根堆 的堆顶取出插入大根堆；
这样就能达到，大根堆，小根堆数量保持平衡，同时大根堆中的小的n/2个数，小根堆中是大的n/2个数，
（大根堆堆顶+小根堆堆顶）/2 就是流的中位数

3、合并有序小文件

假设我们有 100 个小文件，每个文件的大小是 100MB，每个文件中存储的都是有序的字符串。我们希望将这些 100 个小文件合并成一个有序的大文件。
思路：利用一个小根堆，把每个文件的第一条记录取出来，放入小根堆中，那么小根堆的堆顶就是这100条记录中顺序最小的记，它为记录A，也是这100个文件中顺序最小的，将这个堆顶追加到准备的大文件。从记录A原来所在的文件中再取出一条记录，放入小根堆，取出堆顶，如此重复...

4、高性能定时器

5、利用堆求 Top K

思路：利用一个size为k的堆，求最大的Top K 用小根堆 ，求最小的Top k用大根堆。
我们可以维护一个大小为 K 的小顶堆，顺序遍历数组，从数组中取出取数据与堆顶元素比较。如果比堆顶元素大，我们就把堆顶元素删除，并且将这个元素插入到堆中；如果比堆顶元素小，则不做处理，继续遍历数组。这样等数组中的数据都遍历完之后，堆中的数据就是前 K 大数据了。

遍历数组需要 O(n) 的时间复杂度，一次堆化操作需要 O(logK) 的时间复杂度，所以最坏情况下，n 个元素都入堆一次，所以时间复杂度就是 O(nlogK)。

    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if(input == null || input.length < k || k <=0 || input.length == 0){
            return new ArrayList<>();
        }
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k,(x,y)->y-x);
        for(int i = 0;i<k;i++){
            maxHeap.add(input[i]);
        }
        for(int i = k ;i<input.length;i++){
            if(input[i] < maxHeap.peek()){
                maxHeap.poll();
                maxHeap.add(input[i]);
            }
        }
        return new ArrayList<>(maxHeap);
    }

6、假设现在我们有一个包含 10 亿个搜索关键词的日志文件，如何能快速获取到热门榜 Top 10 的搜索关键词呢，单机，可以使用的内存为 1GB？

使用map<key,count>计数，count放入小根堆中，多个小根堆合并求top10.
分析：假设一条搜索50个字节，10亿条那么就占用了50GB的大小，所以一次对所有数据进行统计是不可行的。
0、准备10个空文件
1、采用hash 算法将日志进行计算之后得到hash值，模10，存放入对应的文件中。那么每个文件大概会有1亿条记录，假设平均每条关键词重复10次，那么就是1000万条关键词，大概500MB，1G的内存是可以存下的
2、使用hashmap对每个小文件中的关键词进行数量统计，对每个小文件的统计的结果存入一个Size为10 的小根堆。
3、对这10个小根堆再进行合并得到最终的Top 10 的搜索关键词

7、赫夫曼编码、图的最短路径、最小生成树算法

推荐阅读：
数据结构和算法|堆的应用