AI 助理
备案控制台
开发者社区 人工智能 文章 正文

C++【STL】之priority_queue学习

2023-06-23 86
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： C++ STL 优先级队列，常用接口的使用和模拟实现详细讲解，干货满满！

优先级队列

优先级队列priority_queue也是STL库中容器适配器的一种，常用于进行数据优先级的处理，说到这儿是不是发现有些熟悉，没错它和我们之前讲解的堆本质上就是一个东西，底层都是数组存储的完全二叉树，它在STL库中进行了完美的封装并加入了泛型编程的思想呈现出来

1. 优先级队列的使用

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

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

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

  4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
    empty()：检测容器是否为空
    size()：返回容器中有效元素个数
    front()：返回容器中第一个元素的引用
    push_back()：在容器尾部插入元素

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

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

1.1 构造函数

优先级队列有两种构造方式，可以使用默认构造一个空对象，也可以通过迭代器区间进行构造

==默认构造==

int main()
{
    priority_queue<int> pq;    //默认构造一个空对象
    cout << typeid(pq).name() << endl;
    return 0;
}

默认的比较方式为less，会生成大堆

==迭代器区间构造==

int main()
{
   
   
    vector<int> v = {
   
    1, 2, 3, 4, 5, 6 };
    priority_queue<int, deque<int>, greater<int>> pq(v.begin(), v.end());    //生成小堆
    cout << typeid(pq).name() << endl;

    while (!pq.empty())
    {
   
   
        //打印堆中元素
        cout << pq.top() << " ";
        pq.pop();
    }
    return 0;
}

这里将比较方式改为 greater 后，就会生成 小堆

1.2 常用接口

这里列举常用接口的使用，感兴趣的大佬们可以前往官方文档了解更多细节

  • empty()接口：判空
  • size()接口：查看大小
  • top()接口：查看堆顶元素
  • push()：向堆中插入元素
  • pop()：删除堆顶元素
int main()
{
   
   
    vector<int> v = {
   
    24,45,33,12,65,88,52,66 };
    priority_queue<int> pq(v.begin(), v.end());    //默认生成大堆

    cout << "empty：" << pq.empty() << endl; //判空
    cout << "size：" << pq.size() << endl; //查看大小
    cout << "top：" << pq.top() << endl; //查看堆顶元素
    cout << "------------------------" << endl;

    //插入操作
    pq.push(8);
    pq.push(112);
    cout << "empty：" << pq.empty() << endl;
    cout << "size：" << pq.size() << endl;
    cout << "top：" << pq.top() << endl;
    cout << "------------------------" << endl;

    //删除堆顶元素
    pq.pop();
    pq.pop();
    cout << "empty：" << pq.empty() << endl;
    cout << "size：" << pq.size() << endl;
    cout << "top：" << pq.top() << endl;
    cout << "------------------------" << endl;
    return 0;
}

1.3 优先级切换

创建优先级队列时，默认的比较方式缺省值为less，使用的是仿函数，默认生成大堆，想要创建小堆的话，需要将比较方式设置为grater，不过小于less是大堆，大于grater是小堆，嗯...这就点奇怪

==注意：==

如果要修改比较方式的话，模板参数2的底层容器也需要指明，因为比较方式是模板参数3，缺省参数规定不能跳跃缺省

priority_queue<int, deque<int>, greater<int>> pq(v.begin(), v.end());    //生成小堆

2. 优先级队列模拟实现

我们先来实现没有加入仿函数的版本

2.1 push方法

插入数据，只需尾插数据，然后遵循大小堆的规则将父子节点进行比较，向上调整即可

//向上调整
void adjust_up(int child)
{
   
   
    int parent = (child - 1) / 2;
    while (child > 0)
    {
   
   
        //大堆 parent > chiled
        if (_con[child] > _con[parent])
        {
   
   
            swap(_con[child], _con[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
   
   
            break;
        }
    }
}

void push(const T& val)
{
   
   
    _con.push_back(val);
    adjust_up(_con.size() - 1);
}

2.2 pop方法

删除数据，只需将堆顶数据交换到堆底，删除堆底元素，然后遵循大小堆的规则将父子节点进行比较，从堆顶向下调整即可

//向下调整
void adjust_down(int parent)
{
   
   
    size_t child = parent * 2 + 1;
    while (child < _con.size())
    {
   
   
        if (child + 1 < _con.size()
            && _con[child + 1] > _con[child) //找出较大的孩子
        {
   
   
            ++child;
        }

        //大堆 parent > 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);
}

2.3 判空大小堆顶

empty()方法：判空，复用底层容器的判空接口即可

bool empty()
{
   
   
    return _con.empty();
}

size()方法：查看大小，复用底层容器查看大小接口即可

size_t size()
{
   
   
    return _con.size();
}

top()方法：查看堆顶元素：返回数组首元素即可

const T& top()
{
   
   
    return _con[0];
}

想要使用小堆的话需要将代码中的 > 改为 <，这样的手动切换方式，就显得太挫了，那么是否有姐解决方法呢？答案是有的，那就是本文的周重头戏，使用仿函数来解决

2.4 仿函数

仿函数的主要作用是 借助类和运算符重载，做到同一格式兼容所有函数

下面我们用两个比较大小的仿函数来解决上面优先级队列的实现中不能大小堆自由切换的问题

template<class T>
struct less
{
   
   
    bool operator()(const T& x, const T& y)
    {
   
   
        return x < y;
    }
};

template<class T>
struct greater
{
   
   
    bool operator()(const T& x, const T& y)
    {
   
   
        return x > y;
    }
};

再加入第三个模板参数，也就是用于比较大小的仿函数，缺省值为less

template<class T, class Container = vector<T>, class Comapre = less<T>>

当需要进行逻辑比较时，只需要调用 operator() 进行比较即可

下面来改写向上调整和向下调整

void adjust_up(int child)
{
   
   
    Comapre com;
    int parent = (child - 1) / 2;
    while (child > 0)
    {
   
   
        //child > parent -> parent < child
        //if (Comapre()(_con[parent], _con[child]) //匿名
        if (com(_con[parent], _con[child]))
        {
   
   
            swap(_con[child], _con[parent]);
            child = parent;
            parent = (child - 1) / 2;
        }
        else
        {
   
   
            break;
        }
    }
}

void adjust_down(int parent)
{
   
   
    size_t child = parent * 2 + 1;
    while (child < _con.size())
    {
   
   
        Comapre com;
        if (child + 1 < _con.size()
            && com(_con[child], _con[child + 1])) //找出较大的孩子
        {
   
   
            ++child;
        }

        //parent < child
        if (com(_con[parent], _con[child]))
        {
   
   
            swap(_con[child], _con[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
   
   
            break;
        }
    }
}

这样就可以实现大小堆的自由切换了

2.5 完整代码

#pragma once
#include <iostream>
#include <list>
#include <vector>
#include <deque>
#include <algorithm>
#include <string>
using namespace std;

namespace sakura
{
   
   
    template<class T>
    struct less
    {
   
   
        bool operator()(const T& x, const T& y)
        {
   
   
            return x < y;
        }
    };

    template<class T>
    struct greater
    {
   
   
        bool operator()(const T& x, const T& y)
        {
   
   
            return x > y;
        }
    };

    template<class T, class Container = vector<T>, class Comapre = less<T>>
    class priority_queue
    {
   
   
    public:
        void adjust_up(int child)
        {
   
   
            Comapre com;
            int parent = (child - 1) / 2;
            while (child > 0)
            {
   
   
                //child > parent -> parent < child
                //if (Comapre()(_con[parent], _con[child]) //匿名
                if (com(_con[parent], _con[child]))
                {
   
   
                    swap(_con[child], _con[parent]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else
                {
   
   
                    break;
                }
            }
        }

        void adjust_down(int parent)
        {
   
   
            size_t child = parent * 2 + 1;
            while (child < _con.size())
            {
   
   
                Comapre com;
                if (child + 1 < _con.size()
                    && com(_con[child], _con[child + 1])) //找出较大的孩子
                {
   
   
                    ++child;
                }

                //parent < child
                if (com(_con[parent], _con[child]))
                {
   
   
                    swap(_con[child], _con[parent]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else
                {
   
   
                    break;
                }
            }
        }

        void push(const T& val)
        {
   
   
            _con.push_back(val);
            adjust_up(_con.size() - 1);
        }

        void pop()
        {
   
   
            swap(_con[0], _con[_con.size() - 1]);
            _con.pop_back();
            adjust_down(0);
        }

        const T& top()
        {
   
   
            return _con[0];
        }

        size_t size()
        {
   
   
            return _con.size();
        }

        bool empty()
        {
   
   
            return _con.empty();
        }

    private:
        Container _con;
    };

C++【STL】之priority_queue学习，到这里就介绍结束了，本篇文章对你由帮助的话，期待大佬们的三连，你们的支持是我最大的动力！

文章有写的不足或是错误的地方，欢迎评论或私信指出，我会在第一时间改正！

文章标签：
C++
容器
算法
存储
关键词：
C++ stl
C++学习
C++ priority_queue
C++ stl priority_queue
C++ stl学习
诚酱
目录
相关文章
土木林森
|
21天前
|
算法 C语言 C++
C++语言学习指南：从新手到高手，一文带你领略系统编程的巅峰技艺！
【8月更文挑战第22天】C++由Bjarne Stroustrup于1985年创立，凭借卓越性能与灵活性，在系统编程、游戏开发等领域占据重要地位。它继承了C语言的高效性，并引入面向对象编程，使代码更模块化易管理。C++支持基本语法如变量声明与控制结构；通过`iostream`库实现输入输出；利用类与对象实现面向对象编程；提供模板增强代码复用性；具备异常处理机制确保程序健壮性；C++11引入现代化特性简化编程；标准模板库(STL)支持高效编程；多线程支持利用多核优势。虽然学习曲线陡峭，但掌握后可开启高性能编程大门。随着新标准如C++20的发展，C++持续演进，提供更多开发可能性。
土木林森
41 0
兰雪簪轩
|
15天前
|
存储 算法 编译器
[C++] STL简介
[C++] STL简介
兰雪簪轩
11 1
土木林森
|
21天前
|
存储 算法 C++
C++ STL应用宝典：高效处理数据的艺术与实战技巧大揭秘！
【8月更文挑战第22天】C++ STL（标准模板库）是一组高效的数据结构与算法集合，极大提升编程效率与代码可读性。它包括容器、迭代器、算法等组件。例如，统计文本中单词频率可用`std::map`和`std::ifstream`实现；对数据排序及找极值则可通过`std::vector`结合`std::sort`、`std::min/max_element`完成；而快速查找字符串则适合使用`std::set`配合其内置的`find`方法。这些示例展示了STL的强大功能，有助于编写简洁高效的代码。
土木林森
31 2
小狮子安度因1
|
27天前
|
安全 编译器 容器
C++STL容器和智能指针
C++STL容器和智能指针
小狮子安度因1
15 0
大柏怎么被偷了
|
30天前
|
算法 安全 Linux
【C++】认识STL
【C++】认识STL
大柏怎么被偷了
25 0
小余大牛成长记
|
2月前
|
存储 安全 编译器
【C++入门 四】学习C++内联函数 | auto关键字 | 基于范围的for循环(C++11) | 指针空值nullptr(C++11)
【C++入门 四】学习C++内联函数 | auto关键字 | 基于范围的for循环(C++11) | 指针空值nullptr(C++11)
小余大牛成长记
46 2
小余大牛成长记
|
2月前
|
人工智能 分布式计算 Java
【C++入门 一 】学习C++背景、开启C++奇妙之旅
【C++入门 一 】学习C++背景、开启C++奇妙之旅
小余大牛成长记
36 1
დ旧言~
|
2月前
|
存储 算法 Java
【C++】优先级队列priority_queue模拟实现&&仿函数
【C++】优先级队列priority_queue模拟实现&&仿函数
დ旧言~
23 1
小余大牛成长记
|
2月前
|
存储 自然语言处理 编译器
【C++入门 三】学习C++缺省参数 | 函数重载 | 引用
【C++入门 三】学习C++缺省参数 | 函数重载 | 引用
小余大牛成长记
36 1
小余大牛成长记
|
2月前
|
小程序 C++
【C++入门 二 】学习使用C++命名空间及其展开
【C++入门 二 】学习使用C++命名空间及其展开
小余大牛成长记
38 1