一文带你掌握 优先级队列

news/2024/5/20 8:17:48 标签: stl, 算法, 堆, 排序, 数据结构

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

前言

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

目录

  • 前言
  • 一、优先级队列(priority_queue)介绍
    • 🍉堆的简单介绍:
  • 二、priority_queue接口介绍
    • 2.1 利用优先级队列排序(降序)
    • 2.2 利用优先级队列排序(升序)
  • 三、priority_queue模拟实现
    • 3.1 构造函数
      • 🍔仿函数介绍
    • (2) push()
    • (3) pop()
  • 四、模拟实现总代码:

一、优先级队列(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;
}

运行结果:

57 12 9 7 5 3 1 -3 -5

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

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

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

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

表头表头
class T优先级队列中的数据类型
class Sequence = vector<T>底层采用的数据结构
class Compare = less<typename Sequence::value_type>堆中的比较方法,默认是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;
}

运行结果:

-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;
    }
};

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

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

构造函数:
template <class T, class Container = vector, class Compare = less >
在上面的"利用优先级队列排序(升序)"中已经列出了表格中参数的含义.

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)迭代器区间构造
将迭代器区间的值依次插入(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;
    }
}

(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;//此时表示不需要再交换了
    }
}

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

四、模拟实现总代码:

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

#include <iostream>
#include <queue>
#include<vector>
#include<functional>
#include <algorithm>
#include <assert.h>
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;   //比较方法
    };
};

http://www.niftyadmin.cn/n/5062630.html

相关文章

浅谈OV SSL 证书的优势

浅谈OV SSL 证书的优势

随着网络威胁日益增多&#xff0c;保护网站和用户安全已成为每个企业和组织的重要任务。在众多SSL证书类型中&#xff0c;OV&#xff08;Organization Validation&#xff09;证书以其独特的优势备受关注。让我们深入探究OV证书的优势所在&#xff0c;为网站安全搭建坚实的防线…
阅读更多...
阿里云PolarDB自研数据库详细介绍_兼容MySQL、PostgreSQL和Oracle语法

阿里云PolarDB自研数据库详细介绍_兼容MySQL、PostgreSQL和Oracle语法

阿里云PolarDB数据库是阿里巴巴自研的关系型分布式云原生数据库&#xff0c;PolarDB兼容三种数据库引擎&#xff1a;MySQL、PostgreSQL、Oracle&#xff08;语法兼容&#xff09;&#xff0c;目前提供云原生数据库PolarDB MySQL版、云原生数据库PolarDB PostgreSQL版和云原生数…
阅读更多...
网络运营对职业发展有什么用

网络运营对职业发展有什么用

大家好&#xff0c;我是网络工程师成长日记实验室的郑老师&#xff0c;您现在正在查看的是网络工程师成长日记专栏&#xff0c;记录网络工程师日常生活的点点滴滴 有个哥们联系我&#xff0c;他说他以前是做it售前&#xff0c;也做过售后&#xff0c;也做it很长时间了&#xff…
阅读更多...
【算法系列篇】哈希表

【算法系列篇】哈希表

文章目录 前言1. 两数之和1.1 题目要求1.2 做题思路1.3 Java代码实现 2. 判断是否为字符重排2.1 题目要求2.2 做题思路2.3 Java代码实现 3. 存在重复元素3.1 题目要求3.2 做题思路3.3 Java代码实现 4. 存在重复元素II4.2 题目要求4.2 做题思路4.3 Java代码实现 5. 字母异位词分…
阅读更多...
【算法优选】双指针专题——贰

【算法优选】双指针专题——贰

文章目录 &#x1f60e;前言&#x1f332;[快乐数](https://leetcode.cn/problems/happy-number/)&#x1f6a9;题目描述&#x1f6a9;题⽬分析&#xff1a;&#x1f6a9;算法思路&#xff1a;&#x1f6a9;代码实现&#xff1a; &#x1f38b;[盛水最多的容器](https://leetco…
阅读更多...
打开泰坦陨落2找不到msvcp120.dll无法执行代码/msvcr120.dll丢失修复方法

打开泰坦陨落2找不到msvcp120.dll无法执行代码/msvcr120.dll丢失修复方法

msvcp120.dll 是 Windows 操作系统中的一个动态链接库文件&#xff0c;对于许多程序和游戏的运行起着至关重要的作用。然而&#xff0c;有时候我们可能会遇到 msvcp120.dll 丢失的情况&#xff0c;导致电脑出现各种问题。本文将详细介绍 msvcp120.dll 丢失的四种解决方法&#…
阅读更多...
xcode15-mergeable libraries

xcode15-mergeable libraries

动态链接库(dynamic frameworks) 一般在动态链接库中的symbols并不会被包含到app的二进制文件中&#xff0c;一般是在app bundle的frameworks 文件下&#xff0c;会在app launch的时候加载这个动态链接库&#xff0c;这会花费app的启动时间 静态链接库(static libraries) 会…
阅读更多...
环形链表[简单]

环形链表[简单]

优质博文&#xff1a;IT-BLOG-CN 一、题目 给你一个链表的头节点head&#xff0c;判断链表中是否有环。 如果链表中有某个节点&#xff0c;可以通过连续跟踪next指针再次到达&#xff0c;则链表中存在环。为了表示给定链表中的环&#xff0c;评测系统内部使用整数pos来表示链…
阅读更多...
最新文章

Copyright @ 2022~2023