【C++:STL之栈和队列 | 模拟实现 | 优先级队列 】(二)

简介: 【C++:STL之栈和队列 | 模拟实现 | 优先级队列 】(二)

6 priority_queue的介绍和使用

6.1 priority_queue的介绍

priority_queue的介绍

1. 优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的(默认情况)。

2. 此上下文类似于堆,在堆中可以随时插入元素,并且只能检索最大堆元素(优先队列中位于顶部的元素)。

3. 优先队列被实现为容器适配器,容器适配器即将特定容器类封装作为其底层容器类,queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出,其称为优先队列的顶部。

4. 底层容器可以是任何标准容器类模板,也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问,并支持以下操作:

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

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

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

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

5. 标准容器类vector和deque满足这些需求。默认情况下,如果没有为特定的priority_queue类实例化指定容器类,则使用vector。

6. 需要支持随机访问迭代器,以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

6.2 priority_queue的使用

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

忘记了堆的老铁可以去看看博主讲解的这篇文章:

http://xn--http-u76a//t.csdn.cn/Buh2Q%E2%80%8B

函数声明

接口说明

priority_queue()   priority_queue(first, last)

构造一个空的优先级队列

empty( )

检测优先级队列是否为空,是返回true,否则返回false

top( )

返回优先级队列中最大(最小元素),即堆顶元素

push(x)

在优先级队列中插入元素x

pop( )

删除优先级队列中最大(最小)元素,即堆顶元素

我们可以来试试:

  priority_queue<int> pq;//仿函数为less,默认建立大堆
  pq.push(10);
  pq.push(1);
  pq.push(8);
  pq.push(3);
  pq.push(15);
  pq.push(16);
  while (!pq.empty())
  {
    cout << pq.top() << " ";
    pq.pop();
  }

31512f94bc8e4cc49f2908db1e684434.png

至于为啥仿函数为less,但是建立的确是大堆这个是大佬们硬性规定的,大家也不要太过于较真。

要实现建立小堆我们调用一下greater仿函数即可。

  priority_queue<int,vector<int>,greater<int>> pq;//显示调用仿函数为greater,建立小堆
  pq.push(10);
  pq.push(1);
  pq.push(8);
  pq.push(3);
  pq.push(15);
  pq.push(16);
  while (!pq.empty())
  {
    cout << pq.top() << " ";
    pq.pop();
  }

运行结果:

8833063a9deb4cdf826d5e612c908aa6.png

假如我们想比较自定义类型的大小应该咋办?直接用STL自带的仿函数好像并不能够完成,所以我们还得自己再实现一下仿函数。

先把日期类给整出来:

class Date
{
  friend ostream& operator<<(ostream& out, const Date& d);//友元声明
private:
  int _year;
  int _month;
  int _day;
public:
  Date(int year = 1, 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);
  }
};
ostream& operator<<(ostream& out, const Date& d)
{
  out << d._year << "/" << d._month << "/" << d._day << endl;
  return out;
}

大家这时心里可能会想:重载>>还好理解,因为要输出结果嘛,为啥你要重载>和<运算符呀?

不知道大家忘记了没,当我们建堆时有两种调整方式,向上调整和向下调整时都会设计数据的比较,内置类型没事,自定义类型就得我们重载比较运算符了,所以我们要想实现自定义类型的比较,这个是必不可少的。

然后我们就可以实现日期类的比较了:

  priority_queue<Date, vector<Date>> pq;
  pq.push(Date(2023, 2, 7));
  pq.push(Date(2021, 2, 9));
  pq.push(Date(2023, 2, 8));
  pq.push(Date(2024, 2, 6));
  while(!pq.empty())
  {
    cout << pq.top() ;
    pq.pop();
  }

运行结果:

0af7c687deb944389fa87aeff6c7fa31.png

但是假如我们push的是日期类的地址,用系统自带的仿函数能够完成吗?

大家想想,由于push的是地址,所以比较的是地址的大小而不是地址指向的内容的大小,所以这种方法肯定是不合理的。

我们可以来试试:

0f19c60d9d204e0a80163556960cd73f.png

很明显结果是不对的,尽管有时候碰巧结果恰好对的,也只是运气而已。

即我们还得自己写仿函数:

仿函数:

  struct p_date_less
  {
    bool operator()(Date*& pd1, Date*& pd2)
    {
      return *pd1 < *pd2;
    }
  };
  struct p_date_greater
  {
    bool operator()(Date*& pd1, Date*& pd2)
    {
      return *pd1 > *pd2;
    }
  };

这样就能够正确比较了:

2416d81fadb0450fbe48ee6f5da623f2.png

7 priority_queue的模拟实现

  template<class T, class Container = vector<T>, class Compare = less<T>>
  class priority_queue
  {
  private:
    Container _con;
    void adjust_up(size_t child)//假设这里要建立大堆,默认仿函数是less
    {
      size_t parent = child - 1 >> 1;
      while (child > 0)
      {
        //if (_con[child] > _con[parent])
        Compare cmp;//实例化出一个Cmpare的对象
        if (cmp(_con[parent],_con[child]))//由于仿函数中实现的是x<y
        {
          swap(_con[child], _con[parent]);
          child = parent;
          parent = child - 1 >> 1;
        }
        else
          break;
      }
    }
    void adjust_down(size_t parent)
    {
      size_t child = parent * 2 + 1;
      while (child < _con.size())
      {
        Compare cmp;//实例化出一个Cmpare的对象
        if (child + 1 < _con.size() && cmp(_con[child],_con[child+1]))//假如建立大堆,默认仿函数为less,就得满足_con[child]<_con[child+1]
          child += 1;
        //if (_con[child] > _con[parent])
        if (cmp(_con[parent],_con[child]))//由于仿函数中实现的是x<y
        {
          swap(_con[child], _con[parent]);
          parent = child;
          child = parent * 2 + 1;
        }
        else
          break;
      }
    }
  public:
    priority_queue()
    {
    }
    template<class InputIterator>
    priority_queue(InputIterator first, InputIterator last)
      :_con()
    {
      for (int i = _con.size() - 2 >> 1; i >= 0; i--)//向下建堆时间复杂度为O(N)
        adjust_down(i);
    }
    void push(const T& x)
    {
      _con.push_back(x);
      adjust_up(_con.size() - 1);
    }
    void pop()
    {
      swap(_con[0], _con[size() - 1]);
      _con.pop_back();
      adjust_down(0);
    }
    const T& top()
    {
      return _con.front();
    }
    bool empty()
    {
      return _con.empty();
    }
    size_t size()
    {
      return _con.size();
    }
  };

这个之前在堆那一部分做了较为详细的讲解,这里就不在多说了。

Fox!
+关注
目录
打赏
0
0
0
0
2
分享
相关文章
|
1月前
|
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
142 77
|
1月前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
38 7
|
1月前
|
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
44 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【C++篇】深度解析类与对象(下)
在上一篇博客中,我们学习了C++的基础类与对象概念,包括类的定义、对象的使用和构造函数的作用。在这一篇,我们将深入探讨C++类的一些重要特性,如构造函数的高级用法、类型转换、static成员、友元、内部类、匿名对象,以及对象拷贝优化等。这些内容可以帮助你更好地理解和应用面向对象编程的核心理念,提升代码的健壮性、灵活性和可维护性。
【C++篇】深度解析类与对象(中)
在上一篇博客中,我们学习了C++类与对象的基础内容。这一次,我们将深入探讨C++类的关键特性,包括构造函数、析构函数、拷贝构造函数、赋值运算符重载、以及取地址运算符的重载。这些内容是理解面向对象编程的关键,也帮助我们更好地掌握C++内存管理的细节和编码的高级技巧。
【C++篇】深度解析类与对象(上)
在C++中,类和对象是面向对象编程的基础组成部分。通过类,程序员可以对现实世界的实体进行模拟和抽象。类的基本概念包括成员变量、成员函数、访问控制等。本篇博客将介绍C++类与对象的基础知识,为后续学习打下良好的基础。
|
1月前
|
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
70 19
【C++面向对象——类与对象】CPU类(头歌实践教学平台习题)【合集】
声明一个CPU类,包含等级(rank)、频率(frequency)、电压(voltage)等属性,以及两个公有成员函数run、stop。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。​ 相关知识 类的声明和使用。 类的声明和对象的声明。 构造函数和析构函数的执行。 一、类的声明和使用 1.类的声明基础 在C++中,类是创建对象的蓝图。类的声明定义了类的成员,包括数据成员(变量)和成员函数(方法)。一个简单的类声明示例如下: classMyClass{ public: int
51 13
【C++面向对象——继承与派生】派生类的应用(头歌实践教学平台习题)【合集】
本实验旨在学习类的继承关系、不同继承方式下的访问控制及利用虚基类解决二义性问题。主要内容包括: 1. **类的继承关系基础概念**:介绍继承的定义及声明派生类的语法。 2. **不同继承方式下对基类成员的访问控制**:详细说明`public`、`private`和`protected`继承方式对基类成员的访问权限影响。 3. **利用虚基类解决二义性问题**:解释多继承中可能出现的二义性及其解决方案——虚基类。 实验任务要求从`people`类派生出`student`、`teacher`、`graduate`和`TA`类,添加特定属性并测试这些类的功能。最终通过创建教师和助教实例,验证代码
53 5
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等