c++的堆heap操作

一直使用c++的priority_queue，也知道它底层是一些堆操作，但最近因为一些性能原因，需要在priority_queue筛选一定量的数据之后，拿到结果，结果不要求严格排序，而priority_queue好像是不支持这样的操作，也没有data()之类的方法，当然可以依次出队列来取出所有数据，这其实是完成了一次堆排序，完全是浪费计算。看了下priority_queue的实现，原来只是使用了algorithm里定义的一些堆操作函数而已，我居然之前没留意到过。说实话，尽管priority_queue封装起来好用，名称和作用也非常贴切，不过对于学过数据结构的人来说，理解起来反而不太顺，而push_heap和pop_heap之类的名字理解起来更顺些。

基本使用记录于此。

using namespace std;
struct Student
{
    int age;
    string name;
};

struct StudentCmp
{
    inline bool operator()(const Student &s1, const Student &s2) const {
        return s1.age < s2.age;
    }
};

int main()
{
    vector<Student> v = {
        {9, "s1"},
        {3, "s2"},
        {4, "s3"},
        {1, "s4"},
        {2, "s5"},
        {8, "s6"},
        {6, "s7"},
        {0, "s8"},
        {7, "s9"}
    };
    make_heap(v.begin(), v.end(), StudentCmp());
    cout << v.front().age << endl;
    sort_heap(v.begin(), v.end(), StudentCmp());
    for (auto i : v) {
        cout << i.age << "[" << i.name << "]" << " ";
    }
    return 0;
}

注意：comparetor为小于（<），是大根堆，即根为最大值，排序出来结果是从小到大，这跟不加_Compare参数的默认行为一致。跟课本上一样，堆排序分两步，第一步是建堆，就是n[i] < n[2*i + 1] && n[i] < n[2*i + 2]，第二步是依次将首尾数据互换，并维护堆的性质不变。

也可以不使用sort_heap，手动堆排序：

int main()
{
    vector<Student> v = {
        {9, "s1"},
        {3, "s2"},
        {4, "s3"},
        {1, "s4"},
        {2, "s5"},
        {8, "s6"},
        {6, "s7"},
        {0, "s8"},
        {7, "s9"}
    };
    make_heap(v.begin(), v.end(), StudentCmp());
    cout << v.front().age << endl;
    auto it = v.end();
    while (it > v.begin()) {
        pop_heap(v.begin(), it, StudentCmp());
        --it;
    }
    for (auto i : v) {
        cout << i.age << "[" << i.name << "]" << " ";
    }
    return 0;
}

回到最初的问题，筛选数据后，拿到结果数据，而不再乎是否排序。这里举例，筛选出age最小的五个学生：

int main()
{
    vector<Student> vals = {
        {9, "s1"},
        {3, "s2"},
        {4, "s3"},
        {1, "s4"},
        {2, "s5"},
        {8, "s6"},
        {6, "s7"},
        {0, "s8"},
        {7, "s9"}
    };
    vector<Student> v;
    v.reserve(6);
    for (auto i : vals) {
        if (i.age >= v.front().age && v.size() >= 5) {
            continue;
        }
        v.push_back(i);
        push_heap(v.begin(), v.end(), StudentCmp());
        if (v.size() > 5) {
            pop_heap(v.begin(), v.end(), StudentCmp());
            v.pop_back();
        }
        cout << v.front().age << endl;
    }
    //pop_heap(v.begin(), v.end());
    for (auto i : v) {
        cout << i.age << "[" << i.name << "]" << " ";
    }
    return 0;
}

注意：感觉push_back和push_heap，pop_heap和pop_back()是配套使用的，很有对称感。push_heap()的pop_heap()的第二个参数会有点点奇怪，其实v.end()-1的位置才是要push的数据和要pop的结果，c++库内部做了这层转换，让函数使用更美感。尽管筛选结果是5个，但是有先push后pop的操作，所以reserve()为6.