海量数据处理问题（Top k问题）的实现

    在很多互联网公司的面试题中，都可能会问到海量数据处理的题目，比如在几千亿个数据中如何获取10000个最大的数？这其实就是一个Top k问题，如何从亿万级的数据中得到前K个最大或者最小的数字。

    一个复杂度比较低的算法就是利用最小堆算法，它的思想就是：先建立一个容量为K的最小堆，然后遍历这几千亿个数，如果对于遍历到的数大于最小堆的根节点，那么这个数入堆，并且调整最小堆的结构，遍历完成以后，最小堆的数字就是这几千亿个数中最大的K个数了。

    先来介绍一下最小堆：最小堆（小根堆）是一种数据结构，它首先是一颗完全二叉树，并且，它所有父节点的值小于或等于两个子节点的值。最小堆的存储结构（物理结构）实际上是一个数组。

    因为它是一个完全二叉树，对于下标小于 数组.length/2 - 1 时有叶子节点 ， 对于下标为i（基0），其左节点下标为2i + 1，右节点下标为2i + 2。

    最小堆如图所示，对于每个非叶子节点的数值，一定不大于孩子节点的数值。这样可用含有K个节点的最小堆来保存K个目前的最大值(当然根节点是其中的最小数值)。

    每次有数据输入的时候可以先与根节点比较。若不大于根节点，则舍弃；否则用新数值替换根节点数值。并进行最小堆的调整。

    下面就把java代码的实现贴上来把，创建堆的复杂度是O(N)，调整最小堆的时间复杂度为O(logK)，因此Top K算法(问题)时间复杂度为O(NlogK).

class TopK {
    //创建堆
    int[] createHeap(int a[], int k) {
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = a[i];
        }
        //完全二叉树的数组表示中，下标小于等于result.length / 2 - 1才有子节点
        for (int i = result.length / 2 - 1;i >= 0;i--){
            heapify(i,result);
        }
        return result;
    }

    void heapify(int i,int[] result){
        int left = 2 * i + 1;
        int right = 2 * i + 2;

        int smallest = i;
        if (left < result.length && result[left] < result[i]){
            smallest = left;
        }
        if (right < result.length && result[right] < result[smallest]){
            smallest = right;
        }
        if (smallest == i){
            return;
        }
        else {
            int temp = result[i];
            result[i] = result[smallest];
            result[smallest] = temp;
        }
        heapify(smallest,result);
    }

    //调整堆
    void filterDown(int a[], int value) {
        a[0] = value;
        int parent = 0;

        while(parent < a.length){
            int left = 2*parent+1;
            int right = 2*parent+2;
            int smallest = parent;
            if(left < a.length && a[parent] > a[left]){
                smallest = left;
            }
            if(right < a.length && a[smallest] > a[right]){
                smallest = right;
            }
            if(smallest == parent){
                break;
            }else{
                int temp = a[parent];
                a[parent] = a[smallest];
                a[smallest] = temp;
                parent = smallest;
            }
        }
    }

     //遍历数组，并且调整堆
    int[] findTopKByHeap(int input[], int k) {
        int heap[] = this.createHeap(input, k);
        for(int i=k;i<input.length;i++){
            if(input[i]>heap[0]){
                this.filterDown(heap, input[i]);
            }

        }
        return heap;

    }

    public static void main(String[] args) {
        int a[] = { 100,101,5,4,88,89,845,45,8,4,5,8,452,1,5,8,4,5,8,4,588,44444,88888,777777,100000};
        int result[] = new TopK().findTopKByHeap(a, 5);
        for (int temp : result) {
            System.out.println(temp);
        }
    }
}