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

C++【STL】之priority_queue学习

2023-06-23 106
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 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学习
诚酱
目录
相关文章
是乙太呀
|
12天前
|
算法 网络安全 区块链
2023/11/10学习记录-C/C++对称分组加密DES
本文介绍了对称分组加密的常见算法（如DES、3DES、AES和国密SM4）及其应用场景，包括文件和视频加密、比特币私钥加密、消息和配置项加密及SSL通信加密。文章还详细展示了如何使用异或实现一个简易的对称加密算法，并通过示例代码演示了DES算法在ECB和CBC模式下的加密和解密过程，以及如何封装DES实现CBC和ECB的PKCS7Padding分块填充。
是乙太呀
34 4
2023/11/10学习记录-C/C++对称分组加密DES
ephemerals__
|
13天前
|
算法 C语言 C++
【c++丨STL】list的使用
本文介绍了STL容器`list`的使用方法及其主要功能。`list`是一种双向链表结构，适用于频繁的插入和删除操作。文章详细讲解了`list`的构造函数、析构函数、赋值重载、迭代器、容量接口、元素访问接口、增删查改操作以及一些特有的操作接口如`splice`、`remove_if`、`unique`、`merge`、`sort`和`reverse`。通过示例代码，读者可以更好地理解如何使用这些接口。最后，作者总结了`list`的特点和适用场景，并预告了后续关于`list`模拟实现的文章。
ephemerals__
28 7
ephemerals__
|
1月前
|
存储 编译器 C语言
【c++丨STL】vector的使用
本文介绍了C++ STL中的`vector`容器，包括其基本概念、主要接口及其使用方法。`vector`是一种动态数组，能够根据需要自动调整大小，提供了丰富的操作接口，如增删查改等。文章详细解释了`vector`的构造函数、赋值运算符、容量接口、迭代器接口、元素访问接口以及一些常用的增删操作函数。最后，还展示了如何使用`vector`创建字符串数组，体现了`vector`在实际编程中的灵活性和实用性。
ephemerals__
55 4
ephemerals__
|
1月前
|
C语言 C++ 容器
【c++丨STL】string模拟实现（附源码）
本文详细介绍了如何模拟实现C++ STL中的`string`类，包括其构造函数、拷贝构造、赋值重载、析构函数等基本功能，以及字符串的插入、删除、查找、比较等操作。文章还展示了如何实现输入输出流操作符，使自定义的`string`类能够方便地与`cin`和`cout`配合使用。通过这些实现，读者不仅能加深对`string`类的理解，还能提升对C++编程技巧的掌握。
ephemerals__
72 5
ephemerals__
|
1月前
|
存储 编译器 C语言
【c++丨STL】string类的使用
本文介绍了C++中`string`类的基本概念及其主要接口。`string`类在C++标准库中扮演着重要角色，它提供了比C语言中字符串处理函数更丰富、安全和便捷的功能。文章详细讲解了`string`类的构造函数、赋值运算符、容量管理接口、元素访问及遍历方法、字符串修改操作、字符串运算接口、常量成员和非成员函数等内容。通过实例演示了如何使用这些接口进行字符串的创建、修改、查找和比较等操作，帮助读者更好地理解和掌握`string`类的应用。
ephemerals__
51 2
ephemerals__
|
1月前
|
存储 算法 Linux
【c++】STL简介
本文介绍了C++标准模板库（STL）的基本概念、组成部分及学习方法，强调了STL在提高编程效率和代码复用性方面的重要性。文章详细解析了STL的六大组件：容器、算法、迭代器、仿函数、配接器和空间配置器，并提出了学习STL的三个层次，旨在帮助读者深入理解和掌握STL。
ephemerals__
55 0
ephemerals__
|
16天前
|
存储 编译器 C语言
【c++丨STL】vector模拟实现
本文深入探讨了 `vector` 的底层实现原理，并尝试模拟实现其结构及常用接口。首先介绍了 `vector` 的底层是动态顺序表，使用三个迭代器（指针）来维护数组，分别为 `start`、`finish` 和 `end_of_storage`。接着详细讲解了如何实现 `vector` 的各种构造函数、析构函数、容量接口、迭代器接口、插入和删除操作等。最后提供了完整的模拟实现代码，帮助读者更好地理解和掌握 `vector` 的实现细节。
ephemerals__
27 0
梦笔生花伟
|
2月前
|
编译器 C语言 C++
配置C++的学习环境
【10月更文挑战第18天】如果想要学习C++语言，那就需要配置必要的环境和相关的软件，才可以帮助自己更好的掌握语法知识。 一、本地环境设置 如果您想要设置 C++ 语言环境，您需要确保电脑上有以下两款可用的软件，文本编辑器和 C++ 编译器。 二、文本编辑器 通过编辑器创建的文件通常称为源文件，源文件包含程序源代码。 C++ 程序的源文件通常使用扩展名 .cpp、.cp 或 .c。 在开始编程之前，请确保您有一个文本编辑器，且有足够的经验来编写一个计算机程序，然后把它保存在一个文件中，编译并执行它。 Visual Studio Code：虽然它是一个通用的文本编辑器，但它有很多插
梦笔生花伟
68 6
Svan.
|
2月前
|
存储 程序员 C++
C++常用基础知识—STL库(2)
C++常用基础知识—STL库(2)
Svan.
85 5
Svan.
|
2月前
|
存储 自然语言处理 程序员
C++常用基础知识—STL库(1)
C++常用基础知识—STL库(1)
Svan.
77 1