STL源码笔记（15）—堆和优先级队列（二）

淡淡的烟草味﹌ 2022-08-21 15:56 142阅读 0赞

# STL源码笔记（15）—堆和优先级队列 #

优先级队列的源码实现基于heap的操作，底层容器默认是vector。

## 优先级队列简介 ##

优先级队列跟队列类似，一端插入一端删除，不同的是，优先级队列的元素入队后会根据其优先级进行调整，默认情况下优先级高的将优先出队，在SGI STL中，优先级队列的功能保证由heap实现：`stl_heap.h`中，heap的分析见：[STL堆源码分析][STL]

## 优先级队列构造函数 ##

默认情况下，优先级队列使用vector作为底层容器，使用less作为比较函数，其在源码中的定义声明如下：

template <class _Tp, 
              class _Sequence __STL_DEPENDENT_DEFAULT_TMPL(vector<_Tp>),
              class _Compare
              __STL_DEPENDENT_DEFAULT_TMPL(less<typename _Sequence::value_type>) >
    class priority_queue {
    //1.default construct
     priority_queue() : c() {}
     //2.以特定比较函数构造，空的容器
      explicit priority_queue(const _Compare& __x) :  c(), comp(__x) {}
      //3.以特定比较函数和特定容器构造
      priority_queue(const _Compare& __x, const _Sequence& __s) 
        : c(__s), comp(__x) 
        { make_heap(c.begin(), c.end(), comp); }//这里make_heap类似于堆排序中的建堆操作
    };

根据上述定义，如果要使用其他的比较函数，则必须进行如下声明：

class mycmp1
    {
    public:
        mycmp1(){}
        bool operator()(const int &a, const int &b)
        {
            return a < b;
        }
    };
    int main()
    {
        vector<int>a = { 1, 2, 3 };
        priority_queue<int,vector<int>, mycmp1>pq;//方式1
        priority_queue<int,vector<int>, mycmp1>pq1(mycmp1::mycmp1());//方式2
        priority_queue<int,vector<int>, mycmp1>pq2(mycmp1::mycmp1(),a);//方式3
    }

上述声明过程模板实参必不可少。

## 优先级队列操作 ##

> `empty`  
> Test whether container is empty (public member function )
> 
> `size`  
> Return size (public member function )
> 
> `top`  
> Access top element (public member function )
> 
> `push`  
> Insert element (public member function )
> 
> `pop`  
> Remove top element (public member function )

有了heap的操作，上述实现就十分简单了：

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) {
        __STL_TRY {
          c.push_back(__x); //先在尾部插入元素
          push_heap(c.begin(), c.end(), comp);//再对该元素进行入堆操作
        }
        __STL_UNWIND(c.clear());
      }
      void pop() {
        __STL_TRY {
          pop_heap(c.begin(), c.end(), comp);//出堆只是将堆顶元素放到最后
          c.pop_back();//将最后的原堆顶元素弹出
        }
        __STL_UNWIND(c.clear());
      }
    };

## 优先级队列应用 ##

前两天刷leetcode就有碰到用优先级队列解决的问题：[LeetCode347—Top K Frequent Elements][LeetCode347_Top K Frequent Elements]

另外，如果我们要求说是优先级队列要按class中的某个成员变量来进行优先级判定，例如，经典的就是学生3门课成绩优先看数学。

class score
    {
        int math;
        int chinese;
        int english;
    public:
        score(){}
        void print()
        {
            cout << math << " " << chinese << " " << english << " " << endl;
        }
        score(int a, int b, int c)
        {
            math = a;
            chinese = b;
            english = c;
        }
        bool cmp2(const score&sc)
        {
            return math < sc.math;
        }
    };
    class mycmp2
    {
    public:
        mycmp2(){}
        bool operator() (score&sc1, score&sc2)
        {
            return sc1.cmp2(sc2);
        }
    };
    int main()
    {
        vector<score>vec;
        score a(2,0,0);
        score b(1, 0, 0);
        score c(3,0,0);
        vec.push_back(a);
        vec.push_back(b);
        vec.push_back(c);
        priority_queue<score, vector<score>, mycmp2>pq(mycmp2::mycmp2(),vec);
        while (!pq.empty())
        {
            pq.top().print();
            pq.pop();
        }
        system("pause");
        return 0;
    }

结果显示为：

![这里写图片描述][20160506171825137]

[STL]: http://blog.csdn.net/zhangxiao93/article/details/51330582
[LeetCode347_Top K Frequent Elements]: http://blog.csdn.net/zhangxiao93/article/details/51305635
[20160506171825137]: /images/20220724/1331a87d9cbd47bf90ec43754b0cfd57.png