基础三：堆排序(海量数据TOPK)

题目描述

海量数据TOPK的经典问题，找出海量数据中最大的前K个。

输入：

k=3
array=[1,5,70,456,264,483,456,789]

输出：

[456,483,789]

思路：

两个方法可以明显降低时间复杂度，一个是冒泡排序每次找到最大的，时间复杂度为O(KN)，另一个是堆排序，维护一个大小为K的最小堆，时间复杂度为O((lgK)N)，冒泡排序比较简单，着重复习一下建堆和堆排序的过程。

建堆：

建堆的方法有两种，一种是一个一个插入，由下往上调整，一种是从最后一个有叶子节点的节点开始往前遍历，从上往下调整，保证每个子树先成为最小堆。

由下往上调整建堆：

private void swap(int array[], int a, int b){
    int tmp = array[a];
    array[a] = array[b];
    array[b] = tmp;
}
// 由下往上调整
private void downToUp(int array[], int i){
    while (i>0){
        int parent = i/2;
        if (array[parent] > array[i])
            swap(array, parent, i);
        i = parent;
    }
}
// 建立最小堆
public void minHeap(int array[]){
    for (int i = 1; i < array.length; i++){
        downToUp(array, i);
    }
}

由上往下调整建堆：

private void swap(int array[], int a, int b){
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }
// 由上往下调整
private void upToDown(int array[], int i, int size){
    while (2 * i + 1 < size){
        // 注意根节点从0开始，子节点为2*root+1和2*root+2
        int minSon = 2 * i + 1;
        if (minSon + 1 < size && array[minSon + 1] < array[minSon])
            minSon++;
        if (array[i] > array[minSon])
            swap(array, i, minSon);
        i = minSon;
    }
}
// 建立最小堆
public void minHeap(int array[]){
    for (int i = array.length / 2; i >= 0; i--){
        upToDown(array, i, array.length);
    }
}

堆排序：

如果要使用堆排序，还是用第二种方法建堆比较好，可以重用由上往下调整的函数

// 堆排序
public void heapSort(int array[]){
    minHeap(array);
    for (int i = array.length - 1; i>0; i--){
        swap(array, 0, i);
        upToDown(array, 0, i);
    }
}

问题解决：

建堆和堆排序都讲完了，接下来需要解决TOPK问题了，简单的说就是维护一个大小为K的最小堆，初始取K个元素建堆，然后遍历后面的元素，如果比堆顶元素还小，说明它进不了TOPK，等遍历完，TOPK的元素也就确定了，如果需要按从大到小输出的话，再进行一次堆排序过程即可。

代码：

public class Solution {
    private void swap(int array[], int a, int b){
        int tmp = array[a];
        array[a] = array[b];
        array[b] = tmp;
    }
    // 由上往下调整
    private void upToDown(int array[], int i, int size){
        while (2 * i + 1 < size){
            // 注意根节点从0开始，子节点为2*root+1和2*root+2
            int minSon = 2 * i + 1;
            if (minSon + 1 < size && array[minSon + 1] < array[minSon])
                minSon++;
            if (array[i] > array[minSon])
                swap(array, i, minSon);
            i = minSon;
        }
    }
    // 建立最小堆
    public void minHeap(int array[]){
        for (int i = array.length / 2; i >= 0; i--){
            upToDown(array, i, array.length);
        }
    }
    // 堆排序
    private void heapSort(int array[]){
        minHeap(array);
        for (int i = array.length - 1; i>0; i--){
            swap(array, 0, i);
            upToDown(array, 0, i);
        }
    }
    // 找到TOPK
    public int[] TOPK(int k, int array[]) {
        // 1.取前k个元素建最小堆
        int heap[] = new int[k];
        for (int i = 0; i < k; i++){
            heap[i] = array[i];
        }
        minHeap(heap);
        // 2.遍历后面的元素
        for (int i = k; i < array.length; i++){
            // 比最小值大的替换最小的
            if (array[i] > heap[0]){
                heap[0] = array[i];
                upToDown(heap, 0, k);
            }
        }
        // 3.进行一次堆排序
        heapSort(heap);
        return heap;
    }
    /*// 由下往上调整
    private void downToUp(int array[], int i){
        while (i>0){
            int parent = i/2;
            if (array[parent] > array[i])
                swap(array, parent, i);
            i = parent;
        }
    }
    // 建立最小堆
    public void minHeap(int array[]){
        for (int i = 1; i < array.length; i++){
            downToUp(array, i);
        }
    }*/
}