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.

发表于 09-16 11:56   修改于 09-16 12:01   评论:0   阅读:256  



回到顶部

首页 | 关于我 | 关于本站 | 站内留言 | rss
python logo   django logo   tornado logo