33、STL中的priority_queue的实现

2021/7/28 23:10:57

本文主要是介绍33、STL中的priority_queue的实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

priority_queue,优先队列,是一个拥有权值观念的queue,它跟queue一样是顶部入口,底部出口,在插 入元素时,元素并非按照插入次序排列,它会自动根据权值(通常是元素的实值)排列,权值最高,排 在最前面,如下图所示。

 

 

 默认情况下,priority_queue使用一个max-heap完成,底层容器使用的是一般为vector为底层容器,堆heap 为处理规则来管理底层容器实现 。priority_queue的这种实现机制导致其不被归为容器,而是一种容器配 接器。关键的源码如下:

template <class T, class Squence = vector<T>,
        class Compare = less<typename Sequence::value_tyoe> >
class priority_queue{
    ...
protected:
    Sequence c; // 底层容器
    Compare comp; // 元素大小比较标准
public:
    bool empty() const {return c.empty();}
    size_type size() const {return c.size();}
    const_reference top() const {return c.front()}
    void push(const value_type& x)
    {
        c.push_heap(x);
        push_heap(c.begin(), c.end(),comp);
    }
    void pop()
    {
        pop_heap(c.begin(), c.end(),comp);
        c.pop_back();
    }
};

priority_queue的所有元素,进出都有一定的规则,只有queue顶端的元素(权值最高者),才有机会被外 界取用,它没有遍历功能,也不提供迭代器

举个例子:

#include <queue>
#include <iostream>
using namespace std;
int main()
{
    int ia[9] = {0,4,1,2,3,6,5,8,7 };
    priority_queue<int> pq(ia, ia + 9);
    cout << pq.size() <<endl; // 9
    for(int i = 0; i < pq.size(); i++)
    {
        cout << pq.top() << " "; // 8 8 8 8 8 8 8 8 8
    }
    cout << endl;
    while (!pq.empty())
    {
        cout << pq.top() << ' ';// 8 7 6 5 4 3 2 1 0
        pq.pop();
    }
    return 0;
}


这篇关于33、STL中的priority_queue的实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程