利用堆排序来解决topK问题

在这里利用了C++的几个函数（这几个API接口需要algorithm）：

      分享一下如何使用STL里的heap（堆）算法。堆是一个完全二叉树。在STL中，heap是算法的形式提供给我们使用的。包括下面几个函数：

四个最常用的API接口

make_heap: 根据指定的迭代器区间以及一个可选的比较函数，来创建一个heap. O(N).

push_heap: 把指定区间的最后一个元素插入到heap中. O(logN).

pop_heap: 弹出heap顶元素, 将其放置于区间末尾. O(logN).

sort_heap：堆排序算法，通常通过反复调用pop_heap来实现. N*O(logN).

*注：

C++11加入了两个新成员：

is_heap: 判断给定区间是否是一个heap. O(N)

is_heap_until: 找出区间中第一个不满足heap条件的位置. O(N)

因为heap以算法的形式提供，所以要使用这几个api需要包含 #include <algorithm>

class Solution {
public:
    void adjust2(vector<int> &arr,int pos,int size){
        int left = 2*pos+1;
        int right = 2*pos+2;
        int index = pos;
        if(left<size && arr[index]<arr[left]) index = left;
        if(right < size && arr[index]<arr[right]) index  = right;
        if(index != pos){
            swap(arr[index],arr[pos]);
            adjust2(arr,index,size);
        }
        return;
    }

    void make_heap2(vector<int> &arr){
        for(int i=arr.size()-1;i>=1;i--){
            swap(arr[0],arr[i]);
            adjust2(arr,0,i);
        }
    }
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> tmp;
        if(k==0) return tmp;
        for(int i=0;i<k;i++){
            tmp.push_back(arr[i]);;
        }
        make_heap(tmp.begin(),tmp.end(),less<int>());
        for(int i=k;i<arr.size();i++){
            if(arr[i]<tmp[0]){
                tmp[0] = arr[i];
                adjust2(arr,0,k);
            }
        }
        make_heap2(tmp);
        return tmp;
    }
};