C++初阶(十六)优先级队列

简介: C++初阶(十六)优先级队列

一、priority_queue的介绍和使用


1、priority_queue的介绍

  1. 优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的。
  2. 此上下文类似于堆,在堆中可以随时插入元素,并且只能检索最大堆元素(优先队列中位于顶部的元素)。
  3. 优先队列被实现为容器适配器,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出,其称为优先队列的顶部。
  4. 底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问,并支持以下操作:

empty():检测容器是否为空

size():返回容器中有效元素个数

front():返回容器中第一个元素的引用

push_back():在容器尾部插入元素

pop_back():删除容器尾部元素

  1. 标准容器类vector和deque满足这些需求。默认情况下,如果没有为特定的priority_queue类实例化指定容器类,则使用vector。
  2. 需要支持随机访问迭代器,以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。


2、priority_queue的使用

优先级队列默认使用vector作为其底层存储数据的容器,在vector上又使用了堆算法将vector中元素构造成

堆的结构,因此priority_queue就是堆,所有需要用到堆的位置,都可以考虑使用priority_queue。注意:

默认情况下priority_queue是大堆。

  1. 默认情况下,priority_queue是大堆

47931c756eeb4f3989f5693b759a7957.png

2、如果要建小堆,需要改变条件

644047917559401794c2675f42cd6b6c.png

3、如果在priority_queue中放自定义类型的数据,用户需要在自定义类型中提供> 或者< 的重载。

class Date
{
public:
 Date(int year = 1900, int month = 1, int day = 1)
 : _year(year)
 , _month(month)
 , _day(day)
 {}
 bool operator<(const Date& d)const
 {
 return (_year < d._year) ||
 (_year == d._year && _month < d._month) ||
 (_year == d._year && _month == d._month && _day < d._day);
 }
 bool operator>(const Date& d)const
 {
 return (_year > d._year) ||
 (_year == d._year && _month > d._month) ||
 (_year == d._year && _month == d._month && _day > d._day);
 }
 friend ostream& operator<<(ostream& _cout, const Date& d)
 {
 _cout << d._year << "-" << d._month << "-" << d._day;
 return _cout;
 }
private:
 int _year;
 int _month;
 int _day;
};
void TestPriorityQueue()
{
 // 大堆,需要用户在自定义类型中提供<的重载
 priority_queue<Date> q1;
 q1.push(Date(2018, 10, 29));
 q1.push(Date(2018, 10, 28));
 q1.push(Date(2018, 10, 30));
 cout << q1.top() << endl;
 // 如果要创建小堆,需要用户提供>的重载
 priority_queue<Date, vector<Date>, greater<Date>> q2;
 q2.push(Date(2018, 10, 29));
 q2.push(Date(2018, 10, 28));
 q2.push(Date(2018, 10, 30));
 cout << q2.top() << endl;
 }


二、priority_queue的模拟实现


1、无仿函数

namespace bit
{
  template<class T , class Container =vector<int>>
  class priority_queue
  {
  public:
    void adjust_up(int child)
    {
      int parent = (child - 1) / 2;
      while (child > 0)
      {
        if (_con[parent] < _con[child])
        {
          swap(_con[parent], _con[child]);
          child = parent;
          parent = (child - 1) / 2;
        }
        else
        {
          break;
        }
      }
    }
    void push(const T& x)
    {
      _con.push_back(x);
      adjust_up(_con.size() - 1);
    }
    void adjust_down(int parent)
    {
      int child = parent * 2 + 1;
      while (child < _con.size())
      {
        if (child + 1 < _con.size() && _con[child + 1] > _con[child])
        {
          ++child;
        }
        if (_con[parent] < _con[child])
        {
          swap(_con[parent], _con[child]);
          parent = child;
          child = parent * 2 + 1;
        }
        else
        {
          break;
        }
      }
    }
    void pop()
    {
      swap(_con[0], _con[_con.size() - 1]);
      _con.pop_back();
      adjust_down(0);
    }
    bool empty()
    {
      return _con.empty();
    }
    const T& top()
    {
      return _con[0];
    }
  private:
    Container _con;
  };
}


2、带仿函数

namespace bit
{
  template<class T , class Container =vector<int>,class Compare=Less<T>>
  class priority_queue
  {
  public:
    void adjust_up(int child)
    {
      Compare com;
      int parent = (child - 1) / 2;
      while (child > 0)
      {
        if (com(_con[parent], _con[child]))
        {
          swap(_con[child], _con[parent]);
          child = parent;
          parent = (child - 1) / 2;
        }
        else
        {
          break;
        }
      }
    }
    void push(const T& x)
    {
      _con.push_back(x);
      adjust_up(_con.size() - 1);
    }
    void adjust_down(int parent)
    {
      Compare com;
      size_t child = parent * 2 + 1;
      while (child < _con.size())
      {
        if (child + 1 < _con.size()
          && com(_con[child], _con[child + 1]))
        {
          ++child;
        }
        if (com(_con[parent], _con[child]))
        {
          swap(_con[child], _con[parent]);
          parent = child;
          child = parent * 2 + 1;
        }
        else
        {
          break;
        }
      }
    }
    void pop()
    {
      swap(_con[0], _con[_con.size() - 1]);
      _con.pop_back();
      adjust_down(0);
    }
    bool empty()
    {
      return _con.empty();
    }
    const T& top()
    {
      return _con[0];
    }
  private:
    Container _con;
  };
}
int main()
{
  bit::priority_queue<int,vector<int>,Less<int>> v;
  v.push(1);
  v.push(9);
  v.push(8);
  while (!v.empty())
  {
    cout << v.top() << " ";
    v.pop();
  }
  return 0;
}


目录
相关文章
|
1月前
|
缓存 安全 C++
C++无锁队列:解锁多线程编程新境界
【10月更文挑战第27天】
40 7
|
1月前
|
消息中间件 存储 安全
|
18天前
|
存储 设计模式 C++
【C++】优先级队列(容器适配器)
本文介绍了C++ STL中的线性容器及其适配器,包括栈、队列和优先队列的设计与实现。详细解析了`deque`的特点和存储结构,以及如何利用`deque`实现栈、队列和优先队列。通过自定义命名空间和类模板,展示了如何模拟实现这些容器适配器,重点讲解了优先队列的内部机制,如堆的构建与维护方法。
28 0
|
2月前
|
存储 算法 调度
【C++打怪之路Lv11】-- stack、queue和优先级队列
【C++打怪之路Lv11】-- stack、queue和优先级队列
37 1
|
4月前
|
存储 设计模式 算法
【C++】deque以及优先级队列
【C++】deque以及优先级队列
|
5月前
|
存储 算法 Java
【C++】优先级队列priority_queue模拟实现&&仿函数
【C++】优先级队列priority_queue模拟实现&&仿函数
42 1
|
6月前
|
存储 编译器 C++
【C++ 初阶路】--- 类和对象(下)
【C++ 初阶路】--- 类和对象(下)
26 1
|
6月前
|
存储 编译器 C语言
【C++初阶路】--- 类和对象(中)
【C++初阶路】--- 类和对象(中)
29 1
|
5月前
|
存储 算法 C语言
【C++】详解STL的适配器容器之一:优先级队列 priority_queue
【C++】详解STL的适配器容器之一:优先级队列 priority_queue
|
6月前
|
C++ 容器
【c++】优先级队列|反向迭代器(vector|list)
【c++】优先级队列|反向迭代器(vector|list)
43 0