• 一文带你掌握 优先级队列

    🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
    🐻强烈推荐优质专栏: 🍔🍟🌯C++的世界(持续更新中)
    🐻推荐专栏1: 🍔🍟🌯C语言初阶
    🐻推荐专栏2: 🍔🍟🌯C语言进阶
    🔑个人信条: 🌵知行合一
    🍉本篇简介:>:讲解C++优先级队列相关的知识.
    金句分享:
    ✨少年与爱永不老去✨
    ✨即便披荆斩棘✨
    ✨丢失怒骂鲜衣✨

    前言

    本文通过底层实现优先级队列的部分接口,构建优先级队列的步骤图等详细讲解的方式,使读者对优先级队列有深刻的理解.
    建议先学习数据结构中有关 "堆"的知识,否则理解起来是有些难度的.

    目录

    一、优先级队列(priority_queue)介绍

    在C++中，priority_queue是一种标准模板库（STL）容器，通常用于实现优先队列数据结构。它可以在数据结构中自动维护元素的顺序，而不需要手动排序。

    因为priority_queue类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。

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

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

    • push(): 插入元素到队列中。
    • top(): 获取队列中最高优先级的元素。
    • pop(): 删除队列中最高优先级的元素。
    • size(): 返回队列中元素的数量。
    • empty(): 检查队列是否为空

    priority_queue的特点:

    1. 它是一个容器类模板，可以存储任何可比较的类型。
    2. 该容器中的元素按照一定的比较规则（默认为大根堆）排列，允许用户自定义规则。
    3. 它支持快速的插入和删除操作，并且能够在O(1)时间里获取最高优先级的元素。

    补充知识:

    🍉堆的简单介绍:

    大堆和小堆都属于堆的一种。

    大堆:
    在一个堆中，每个父节点的值都大于其子节点的值。也就是说，最大的值在堆的顶部，称为“堆顶”。常用于按从大到小排序的场合。
    意味着大堆适合排降序.
    拷贝是一个手动过程

    小堆:
    在一个堆中，每个父节点的值都小于其子节点的值。也就是说，最小的值在堆的顶部。常用于按从小到大排序的场合。
    意味着小堆适合排升序.

    在这里插入图片描述

    二、priority_queue接口介绍

    在这里插入图片描述

    接口名解释
    empty()判断是否为空的优先级队列
    size()返回优先级队列中有效元素的个数
    top()返回堆顶的数据
    push()将新元素插入进优先级队列
    pop()将堆顶数据删除

    2.1 利用优先级队列排序(降序)

    如果C语言阶段学过堆的友友们对堆应该很了解了.

    这里的优先级队列就是一个堆的结构.

    void test1()
{
	//构造1:
	priority_queue<int> pq1;//创建一个空优先级队列 默认是大堆
	
	//向优先级队列中插入一些数据
	pq1.push(5);
	pq1.push(3);
	pq1.push(8);
	pq1.push(1);
	pq1.push(7);
	pq1.push(9);
	pq1.push(-3);
	pq1.push(2);

	cout << "pq1=  ";
	//大堆遍历出来的结果就是降序
	while (!pq1.empty())		//9 8 7 5 3 2 1 -3
	{
		cout<< pq1.top()<<" ";
		pq1.pop();
	}
	cout << endl;

	//构造2:
	int arr[] = { 3,5,57,1,7,9,-3,-5,12 };
	priority_queue<int> pq2(arr, arr + sizeof(arr) / sizeof(int));//用迭代器区间构造

	cout << "pq2=  ";
	while (!pq2.empty())	// 57 12 9 7 5 3 1 -3 -5
	{
		cout << pq2.top() << " ";
		pq2.pop();
	}

	cout << endl;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37

    运行结果:

    57 12 9 7 5 3 1 -3 -5

    图例:
    插入进优先级队列的过程.
    在这里插入图片描述
    在这里插入图片描述

    所以不难得出,大堆是排序是降序.

    2.2 利用优先级队列排序(升序)

    通过观察源码,我们不难发现,优先级队列有三个模板参数,其中后两个是某仍给出的.

    表头表头
    class T优先级队列中的数据类型
    class Sequence = vector底层采用的数据结构
    class Compare = less堆中的比较方法,默认是less

    在这里插入图片描述
    我们要实现升序排列,则我们需要建小堆,这里就得显示的给出三个模板参数.

    void test2()
{
	int arr[] = { 3,5,57,1,7,9,-3,-5,12 };
	//显示给出这三个模板参数,将比较方法改成greater/建小堆
	priority_queue<int, vector<int>,greater<int>> pq2(arr, arr + sizeof(arr) / sizeof(int));

	//堆顶数据是最小值
    cout << pq2.top() << endl;	//-5

	cout << "test2::pq2=  ";
	while (!pq2.empty())		//-5 -3 1 3 5 7 9 12 57
	{
		cout << pq2.top() << " ";
		pq2.pop();
	}

	cout << endl;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    运行结果:

    -5 -3 1 3 5 7 9 12 57

    三、priority_queue模拟实现

    3.1 构造函数

    比较方法:
    前面说了,优先级队列就是堆,那么堆的算法中,元素的比较方法会决定是大堆还是小堆.

    🍔仿函数介绍

    C++中的仿函数是一种函数对象，它可以像普通函数一样使用，但是它是一个类的对象。

    仿函数可以像函数一样被调用，并且可以在函数调用之间保持状态，这非常有用。

    仿函数的实现方式通常是定义一个类，该类重载了圆括号运算符()，并且可以接受一个或多个参数。圆括号运算符()的实现可以按照需要进行定义，以实现不同的功能。

    // 仿函数/函数对象
template<class T>
class Less
{
public:
    bool operator()(const T& x, const T& y)
    {
        return x < y;
    }
};

template<class T>
class Greater
{
public:
    bool operator()(const T& x, const T& y)
    {
        return x > y;
    }
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20

    Less函数和Greater函数使用示例:

    Less(a,b);
    Greater(a,b);
    他们可以像函数一样正常调用.

    构造函数:
    template
    在上面的"利用优先级队列排序(升序)"中已经列出了表格中参数的含义.

    namespace cjn{
    //模拟实现priority_queue类

    //函数模板,默认底层是vector实现
    template <class T, class Container = vector<T>, class Compare = less<T> >

    class priority_queue{
    public:
        priority_queue()        //默认构造
        :c()
        { }

        template <class InputIterator>

        priority_queue(InputIterator first, InputIterator last) //迭代器区间构造
        {
            while(first!=last)
            {
                push(*first);
                first++;
            }
        }
    private:
        Container c;    //底层容器
        Compare comp;   //比较方法
    };
};

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    (1)默认构造
    只需要调用底层容器的默认构造就行了.(当然,也可以不写,因为会默认调用)

    (2)迭代器区间构造
    将迭代器区间的值依次插入(push())进优先级队列.

    (2) push()

    1. 将数据先尾插进容器.
    2. 将新元素向上调整至合适位置,重新形成优先级队列.
      在这里插入图片描述
    void push(const T& x)
{
    c.push_back(x);     //尾插入堆
    Adjust_Up(c.size()-1);    //将新元素的下标传参,使其向上调整形成堆
}
void Adjust_Up(int child)
{
    int parent=(child-1)/2;
    while(comp(c[parent],c[child]) && child != 0)
    {
        std::swap(c[parent],c[child]);

        //更新 父亲 和 孩子
        child=parent;
        parent=(child-1)/2;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    (3) pop()

    1. 与最后一个元素交换.
    2. 删除交换后的最后一个元素.
    3. 将堆顶元素向下调整.
      在这里插入图片描述
    void pop()
{
    swap(c[0],c[c.size()-1]);       //将堆顶数据与最后一个元素交换
    c.pop_back();                        //删除最后一个元素
    Adjust_Down(0);          //将堆顶数据向下调整
}
void Adjust_Down(int parent)
{
    int child=(parent*2)+1;
    while(child<c.size())
    {
        if (child + 1 < c.size() && comp(c[child], c[child + 1]))//与右孩子比较,注意,也可能不存在 右孩子
        //if(comp(c[child],c[child+1]))       		//错误写法
        {
            child+=1;
        }
        if (comp(c[parent], c[child]))
        {
            std::swap(c[parent], c[child]);

            //更新 父亲 和 孩子
            parent = child;
            child = (parent * 2) + 1;
        }
        else break;//此时表示不需要再交换了
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    其他接口复用底层容器的即可,这里就不过多介绍了.

    四、模拟实现总代码:

    //
// Created by 86132 on 2023/9/5.
//

#include 
#include 
#include
#include
#include 
#include 
using namespace std;

// 仿函数/函数对象
template<class T>
class Less
{
public:
    bool operator()(const T& x, const T& y)
    {
        return x < y;
    }
};

template<class T>
class Greater
{
public:
    bool operator()(const T& x, const T& y)
    {
        return x > y;
    }
};
namespace cjn{
    //模拟实现priority_queue类

    //函数模板,默认底层是vector实现
    template <class T, class Container = vector<T>, class Compare = less<T> >

    class priority_queue{
    public:
        priority_queue()        //默认构造
        :c()
        { }

        template <class InputIterator>

        priority_queue(InputIterator first, InputIterator last) //迭代器区间构造
        {
            while(first!=last)
            {
                push(*first);
                first++;
            }
        }

        bool empty() const
        {
            return c.empty();
        }

        size_t size() const
        {
            return c.size();
        }

       const T& top() const
        {
            assert(!empty());
            return c[0];
        }

        void push(const T& x)
        {
            c.push_back(x);     //尾插入堆
            Adjust_Up(c.size()-1);    //将新元素的下标传参,使其向上调整形成堆
        }

        void pop()
        {
            swap(c[0],c[c.size()-1]);       //将堆顶数据与最后一个元素交换
            c.pop_back();                        //删除最后一个元素
            Adjust_Down(0);          //将堆顶数据向下调整
        }
        void Adjust_Up(int child)
        {
            int parent=(child-1)/2;
            while(comp(c[parent],c[child]) && child != 0)
            {
                std::swap(c[parent],c[child]);

                //更新 父亲 和 孩子
                child=parent;
                parent=(child-1)/2;
            }
        }
        void Adjust_Down(int parent)
        {
            int child=(parent*2)+1;
            while(child<c.size())
            {
                if (child + 1 < c.size() && comp(c[child], c[child + 1]))//与右孩子比较,注意,也可能不存在 右孩子
                //if(comp(c[child],c[child+1]))       
                {
                    child+=1;
                }
                if (comp(c[parent], c[child]))
                {
                    std::swap(c[parent], c[child]);

                    //更新 父亲 和 孩子
                    parent = child;
                    child = (parent * 2) + 1;
                }
                else break;//此时表示不需要再交换了
            }
        }
    private:
        Container c;    //底层容器
        Compare comp;   //比较方法
    };
};



    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
  • 相关阅读:
    ORB-SLAM2从理论到代码实现（九）：LocalMapping程序详解
    X3DAudio1_7.dll丢失原因，X3DAudio1_7.dll丢失怎样解决分享
    智慧大屏是如何实现数据可视化的？
    算法设计与分析_练习三_动态规划算法
    【RAZ】kids 电脑版本
    MVC 框架安全
    Python交叉验证实现
    一行log日志，结果引发了P1的线上事故！
    ＜数据结构＞ - 数据结构在算法比赛中的应用（上）
    腾讯云GPU云服务器计算型GN7有哪些特点？适用于哪些场景？
  • 原文地址：https://blog.csdn.net/qq_67276605/article/details/133485558