STL —— priority_queue容器用法简介

桃扇骨 2022-12-10 14:38 182阅读 0赞

### 文章目录 ###

*   *  priority\_queue介绍
     *  使用
     *  模拟实现

## priority\_queue介绍 ##

1.  优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。(**默认大堆**)
2.  此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
3.  优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
4.  **底层容器可以是任何标准容器类模板**，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：  
    empty()：检测容器是否为空  
    size()：返回容器中有效元素个数  
    front()：返回容器中第一个元素的引用  
    push\_back()：在容器尾部插入元素  
    pop\_back()：删除容器尾部元素
5.  标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定priority\_queue类实例化指定容器类，则**使用vector**。

## 使用 ##

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority\_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority\_queue。

*  **priority\_queue()/priority\_queue(first,last)** 构造一个空的优先级队列
 *  **empty( )** 检测优先级队列是否为空，是返回true，否则返回false
 *  **top( )** 返回优先级队列中最大(最小元素)，即堆顶元素
 *  **push(x)** 在优先级队列中插入元素x
 *  **pop()** 删除优先级队列中最大(最小)元素，即堆顶元素

## 模拟实现 ##

#include <vector>
    #include <algorithm>
    #include <iostream>
    namespace mypri {
        
      //仿函数 函数对象 
      template<class T> 
        struct less {
        
          bool operator()(const T& x1, const T& x2){
        return x1 > x2;} 
        };
      template<class T>
        struct greater {
        
          bool operator()(const T& x1, const T& x2){
        return x1 < x2;}
        };
      //默认大堆
      template<class T, class Container = std::vector<T>, class Compare = less<T> > 
        class priority_queue {
        
          public:
            void Adiustup(int child) {
        //up
              Compare com;//实例化一个对象 当伪函数使用
              int partent = (child -1) / 2;
              while (child > 0) {
        
                if (com(_con[partent], _con[child])) {
        //调整后更新位置
                  std::swap(_con[partent], _con[child]);
                  child = partent;
                  partent = (child-1) / 2;
                }else {
        
                  break;
                }
              }
            }
            void Adjustdown(int root) {
        //down
              Compare com;
              int partent = root;
              int child = 2 * partent + 1;
              while (child < _con.size()) {
        
                if (child + 1 < _con.size() && _con[child] < _con[child+1]) {
        
                  child++;
                }
                if (com(_con[partent], _con[child])) {
        
                  swap(_con[child], _con[partent]);
                  partent = child;
                  child = partent * 2 + 1;
                }else {
        
                  break;
                }
              }
    
            }
            void push(const T& x) {
        
              _con.pushback(x);
              Adjustup(_con,size() - 1);
            }
            void pop() {
        
              swap(_con[0], _con[_con.size()-1]);
              _con.pop_back();
              Adjustdown(0);
            }
            T& top() {
        
              return _con[0];
            }
            size_t size() {
        
              return _con.size();
            }
            bool empty() {
        
              return _con.empty();
            }
          private:
            Container _con;
        };
    
      void test() {
        
        priority_queue<int, std::vector<int>, greater<int> > pro;
        pro.push(1);
        pro.push(1);
        pro.push(7);
        pro.push(4);
        while (!pro.empty()) {
        
          std::cout << pro.top() << " ";
          pro.pop();
        }
        std::cout << std::endl;
      }
    }