【C++】优先队列的使用及模拟实现

💗个人主页💗
⭐个人专栏——C++学习⭐
💫点击关注🤩一起学习C语言💯💫

目录

导读

一、什么是优先队列

二、优先队列的使用

1. 优先队列的构造

2. 优先队列的基本操作

3. 使用示例

三、优先队列模拟实现

1. 仿函数

2. 成员变量

3. 向上调整

4. push函数

5. 向下调整

6. pop函数

7. empty和size

8. top函数

四、完整代码

1. p_queue.h

2. test.cpp

导读

我们上次学习了栈和队列，今天我们来学习优先队列，主要是了解它的一些基本使用和如何模拟实现。

一、什么是优先队列

优先队列（Priority Queue）是一种高效的数据结构，它是队列的一种扩展，不同之处在于每个元素都有一个相关的优先级。在优先队列中，元素不是按照插入的顺序进行排列，而是按照元素的优先级进行排列，优先级高的元素排在前面。

优先队列的定义可以有多种方式，其中一种常见的定义方式是基于堆（Heap）数据结构实现的。堆是一种二叉树，满足以下两个条件：

  1. 堆的根节点是最小或最大元素，即满足最小堆或最大堆的性质。
  2. 堆的每个节点的值都小于或大于其子节点的值，即满足堆的有序性。

基于堆实现的优先队列可以使用数组或链表来表示堆结构，并提供一些基本的操作，如插入元素、删除优先级最高的元素等。插入元素时，根据元素的优先级，将元素插入到合适的位置；删除元素时，取出优先级最高的元素，并保持堆的有序性。

不同于普通队列的FIFO（先进先出）特性，优先队列的元素按照优先级进行排序，具有最高优先级的元素会被最先处理。

特点：

  1. 元素具有优先级：与普通队列不同，优先队列中的元素具有优先级。每个元素都被赋予一个优先级值，用来确定其在队列中的位置。

  2. 按优先级排序：优先队列中的元素按照优先级进行排序。具有最高优先级的元素会被放在队列的最前面。

  3. 自动排序：在插入元素时，优先队列会自动根据元素的优先级进行排序。较高优先级的元素会被排在前面，较低优先级的元素会被排在后面。

  4. 快速访问最高优先级元素：优先队列支持快速访问具有最高优先级的元素。可以通过获取队列的顶部元素来获得具有最高优先级的元素。

  5. 插入和删除操作的时间复杂度：在堆实现的优先队列中，插入和删除元素的平均时间复杂度为O(log n)，其中n是当前队列中的元素个数。

需要注意的是，优先队列并不保证相同优先级的元素的顺序，它只保证具有较高优先级的元素会被优先处理。如果需要保持相同优先级元素的顺序，可以通过自定义比较函数来实现。

二、优先队列的使用

1. 优先队列的构造

默认情况下，priority_queue使用less<int>作为比较器，以使元素按降序排列。也就是大堆。

如果要使用其他比较器或自定义排序规则，可以在创建优先队列对象时传递一个比较器函数对象或lambda表达式。

例如，要使元素按升序排列，可以使用以下代码：

priority_queue<int, vector<int>, greater<int>> pq;

优先队列的构造方式有以下几种：

  1. 默认构造：使用无参构造函数创建一个空的优先队列，例如：priority_queue<int> pq;

  2. 指定容器构造：可以通过指定容器类型和容器对象来构造优先队列。例如，使用vector容器构造一个最大堆优先队列：priority_queue<int, vector<int>> pq;，使用现有的vector对象构造优先队列：vector<int> vec; priority_queue<int, vector<int>> pq(vec);

  3. 指定比较函数构造：可以通过指定一个自定义的比较函数来构造优先队列，以改变默认的元素优先级比较规则。比较函数可以是自定义的函数、函数指针或者函数对象。例如，构造一个从小到大排序的优先队列：priority_queue<int, vector<int>, greater<int>> pq;，构造一个使用自定义比较函数的优先队列：auto cmp = [](int a, int b){ return a % 10 < b % 10; }; priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);

2. 优先队列的基本操作

优先队列的基本操作包括插入元素、删除最高优先级元素、判断队列是否为空等。常用的操作函数有：

  • push(element)：将元素插入到优先队列中。
  • pop()：移除优先队列中的最高优先级元素。
  • top()：返回优先队列中的最高优先级元素。
  • empty()：判断优先队列是否为空，如果为空返回true，否则返回false。
  • size()：返回优先队列中元素的个数。

3. 使用示例

1. 包含头文件：首先需要包含<queue>头文件

#include <queue>

2. 定义优先队列：使用priority_queue类定义一个优先队列对象（默认大堆）

priority_queue<int> pq;

 3. 插入元素：使用push()函数向优先队列中插入元素

pq.push(5);  // 插入元素5
pq.push(2);  // 插入元素2
pq.push(8);  // 插入元素8

4. 访问元素：可以使用top()函数获取具有最高优先级的元素

int highestPriority = pq.top();  // 获取最高优先级元素

 5. 删除元素：使用pop()函数从优先队列中删除具有最高优先级的元素

pq.pop();  // 删除最高优先级元素

完整示例： 

#include <iostream>
#include <queue>
using namespace std;

int main() 
{
    priority_queue<int> pq;

    pq.push(5);
    pq.push(2);
    pq.push(8);

    int highestPriority = pq.top();
    cout << "The highest priority element is: " << highestPriority << endl;

    pq.pop();

    highestPriority = pq.top();
    cout << "The new highest priority element is: " << highestPriority << endl;

    return 0;
}

三、优先队列模拟实现

1. 仿函数

因为我们下面的模拟实现要用到这个知识，所以我们先来了解一下。

仿函数（Functor）是一种重载了圆括号运算符 operator() 的类对象，使其具有函数的行为。通过重载圆括号运算符，我们可以像调用函数一样使用这个类对象来执行某些操作。

仿函数可以将函数调用的语义封装在类对象的操作中，从而具有更多的灵活性和可定制性。它可以接受参数，执行特定的操作，并返回一个结果。

使用仿函数的好处是可以将其作为参数传递给其他函数或容器类（如sort、transform、find_if等），从而实现对容器中的元素进行自定义的操作和排序。

	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. less 类实现了一个比较操作符函数 operator()，用于比较两个元素的大小。它接受两个常引用参数 x 和 y，并返回一个布尔值。在该实现中，它通过 < 运算符来比较 x 和 y 的大小，如果 x 小于 y，则返回 true，否则返回 false。

  2. greater 类与 less 类类似，也实现了一个比较操作符函数 operator()，用于比较两个元素的大小。同样，它接受两个常引用参数 x 和 y，并返回一个布尔值。不同的是，它通过 > 运算符来比较 x 和 y 的大小，如果 x 大于 y，则返回 true，否则返回 false。

这两个仿函数类可以在定义优先队列时作为比较准则的类型参数进行使用，用于指定元素之间的比较规则。

2. 成员变量

下述代码是在C++中定义优先队列（priority_queue）的模板类。优先队列是一种基于堆（heap）的数据结构，它的特点是每次取出的元素都是当前优先级最高的元素。

在模板类的定义中，有三个模板参数：

  1. T：表示元素的类型。
  2. Container：表示底层容器的类型，默认为vector<T>。优先队列使用底层容器来存储元素，可以根据需要选择不同类型的容器。
  3. Compare：表示元素之间的比较准则，默认为less<T>。比较准则是一个仿函数（应用上述提到的仿函数的概念），它定义了如何比较两个元素的优先级。默认情况下，使用less<T>来进行比较，即优先级高的元素被认为是小的元素。

在模板类的私有部分，定义了一个私有变量_con，它是容器类型Container的一个对象，用于存储优先队列的元素。

    template<class T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{
	
	private:
		Container _con;
	};

3. 向上调整

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

上述代码是一个成员函数 adjust_up 的实现，用于调整优先队列中某个节点的位置以保持堆的性质。

在该函数中，首先创建一个 Compare 对象 com，用于进行元素的比较。

然后，根据子节点的索引 child 计算出其父节点的索引，并使用循环进行调整。

在每次循环中，比较父节点和子节点的值，如果父节点的值比子节点的值小（通过调用 com 的 operator() 来比较），则交换两者的位置，并更新子节点和父节点的索引。这样，每次循环都会将较大的值上移一层，直到子节点的值不大于父节点的值或者子节点已经到达根节点。

最终，该函数保证经过调整后，优先队列中的元素按照 Compare 对象 com 所定义的比较准则（通过调用 com 的 operator()）保持了堆的性质。

4. push函数

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

首先，将元素 x 插入到容器 _con 的末尾，使用 push_back 函数。

然后，调用 adjust_up 函数对插入的元素进行上调操作。_con.size() - 1 表示插入元素的索引，即最后一个元素的索引。

adjust_up 函数的作用是将插入的元素与其父节点进行比较并交换，以保持堆的性质。

通过这样的操作，插入的元素将逐步上移，直到满足堆的性质为止。

5. 向下调整

		void adjust_down(size_t parent)
		{
			Compare com;
			size_t child = parent * 2 + 1;
			while (child < _con.size())
			{
				
				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
				{
					++child;
				}

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

以上代码是一个成员函数 adjust_down 的实现，用于在删除元素或进行堆化操作时，将某个节点与其子节点进行比较并交换，以保持堆的性质。

函数接收一个参数 parent，表示要进行调整的节点的索引。

首先，创建一个 Compare 对象 com，用于指定比较准则。

然后，根据节点的索引 parent 计算其左子节点的索引 child，即 child = parent * 2 + 1。

接下来，使用一个循环，不断比较父节点和子节点的值，如果满足交换条件，则进行交换操作。

具体的交换条件如下：

  1. 如果右子节点存在且右子节点的值大于左子节点的值，将 child 增加 1，即指向右子节点。
  2. 如果父节点的值小于子节点的值，进行交换操作，即将父节点和子节点的值互换。
  3. 更新父节点和子节点的索引，父节点变为交换后的子节点，子节点变为新的左子节点。

最后，如果不满足交换条件，则退出循环。

通过这样的操作，被调整的节点将逐渐下移，直到满足堆的性质为止。

6. pop函数

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

首先，使用 swap 函数将堆顶元素 _con[0] 与最后一个元素 _con[_con.size() - 1] 进行交换。

然后，使用 pop_back 函数将最后一个元素删除。

最后，调用 adjust_down 函数对堆顶元素进行调整，以保持堆的性质。

7. empty和size

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

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

empty 函数用于判断堆是否为空，通过调用 _con.empty() 来判断内部容器 _con 是否为空，如果为空则返回 true，否则返回 false。

size 函数用于返回堆中元素的个数，通过调用 _con.size() 来获取内部容器 _con 的大小，即堆中元素的个数，并将其返回。

8. top函数

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

top 函数用于返回堆顶的元素，即堆中最大（或最小）的元素。在该实现中，直接通过 _con[0] 获取堆顶的元素，并将其返回。注意此处返回的是一个常引用 const T&，表示返回的元素不能被修改。

四、完整代码

1. p_queue.h

#pragma once
#include <iostream>

#include <vector>
#include<algorithm>
using namespace std;

namespace Myq_queue
{
	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;
		}
	};

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

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

		void adjust_down(size_t parent)
		{
			Compare com;
			size_t child = parent * 2 + 1;
			while (child < _con.size())
			{
				
				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
				{
					++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);
		}

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

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

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

2. test.cpp

void test_priority_queue()
{

	// 小堆
	Myq_queue::priority_queue<int, vector<int>, Myq_queue::greater<int>> pq;
	pq.push(2);
	pq.push(1);
	pq.push(4);
	pq.push(3);
	pq.push(7);
	pq.push(8);

	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;

}
int main()
{
	test_priority_queue();
	return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/733672.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

[已解决]ImportError: DLL load failed while importing win32api: 找不到指定的程序。

[已解决]ImportError: DLL load failed while importing win32api: 找不到指定的程序。

使用pip install pywin32302安装后import找不到win32api 失败尝试 上网找别人的解决方案&#xff0c;大部分解决方案都是通过复制下面两个dll文件到 下面这个文件夹&#xff0c;并且复制到C:\Windows\System32&#xff0c;从而解决问题&#xff0c;但是我没能成功。 解决方…
阅读更多...
web中间件漏洞-Redis漏洞未授权访问漏洞-写webshell、写ssh公钥

web中间件漏洞-Redis漏洞未授权访问漏洞-写webshell、写ssh公钥

web中间件漏洞-Redis漏洞未授权访问漏洞 利用redis未授权访问漏洞写webshell 利用redis未授权访问、攻击机向服务器写入webshell 从服务器查看写入的webshell 菜刀连接 利用redis未授权访问漏洞写ssh公钥 kali生成rsa公私钥对 ssh-keygen -t rsa 将公钥id_rsa.pub写入文…
阅读更多...
鸿蒙 HarmonyOS NEXT星河版APP应用开发—上篇

鸿蒙 HarmonyOS NEXT星河版APP应用开发—上篇

一、鸿蒙开发环境搭建 DevEco Studio安装 下载 访问官网&#xff1a;https://developer.huawei.com/consumer/cn/deveco-studio/选择操作系统版本后并注册登录华为账号既可下载安装包 安装 建议&#xff1a;软件和依赖安装目录不要使用中文字符软件安装包下载完成后&#xff0…
阅读更多...
HTML(19)——Flex

HTML(19)——Flex

Flex布局也叫弹性布局&#xff0c;是浏览器提倡的布局模型&#xff0c;非常适合结构化布局&#xff0c;提供了强大的空间分布和对齐能力。 Flex模型不会产生浮动布局中脱标现象&#xff0c;布局网页更简单、更灵活。 Flex-组成 设置方式&#xff1a;给父元素设置display:fle…
阅读更多...
以太坊==windows电脑本地搭建一个虚拟的以太坊环境

以太坊==windows电脑本地搭建一个虚拟的以太坊环境

提供不同的选择&#xff0c;适合不同需求和技术水平的开发者&#xff1a; Geth&#xff1a;适合需要与主网兼容或构建私有网络的开发者。Ganache&#xff1a;适合快速开发和测试智能合约的开发者&#xff0c;特别是初学者。Docker&#xff1a;适合需要快速、可重复搭建环境的开…
阅读更多...
四川汇聚荣科技有限公司靠谱吗？

四川汇聚荣科技有限公司靠谱吗？

在如今这个信息爆炸的时代&#xff0c;了解一家公司是否靠谱对于消费者和合作伙伴来说至关重要。四川汇聚荣科技有限公司作为一家位于中国西部地区的企业&#xff0c;自然也受到了人们的关注。那么&#xff0c;这家公司究竟如何呢?接下来&#xff0c;我们将从多个角度进行深入…
阅读更多...
c语言 课设 atm

c语言 课设 atm

功能需求分析 ATM功能主界面：显示所能进行的操作，用户可多次选择。 ATM注册界面：输入用户名，用户密码，确认密码，密码长度不是六位重新输入，两次密码不一致重新输入，输入账号。密码隐藏，实现退格换行对*无影响。多人注册 ATM登录界面：输入账号，密码，三次以内输入…
阅读更多...
NettyのFuturePromise、HandlerPipeline、ByteBuf

NettyのFuturePromise、HandlerPipeline、ByteBuf

本篇介绍Netty的剩下三个组件Future&Promise、Handler&Pipeline、ByteBuf 1、Future&Promise Future和Promise都是Netty实现异步的组件。 1.1、JDK中的future 在JDK中也有一个同名的Future&#xff0c;通常是配合多线程的Callable以及线程池的submit()方法使用&am…
阅读更多...
Rocky Linux 更换CN镜像地址

Rocky Linux 更换CN镜像地址

官方镜像列表&#xff0c;下拉查找 官方镜像列表&#xff1a;https://mirrors.rockylinux.org/mirrormanager/mirrorsCN 开头的站点。 一键更改镜像地址脚本 以下是更改从默认更改到阿里云地址 cat <<EOF>>/RackyLinux_Update_repo.sh #!/bin/bash # -*- codin…
阅读更多...
ChatTTS增强版V3【已开源】，长文本修复，中英混读，导入音色，批量SRT、TXT

ChatTTS增强版V3【已开源】，长文本修复，中英混读，导入音色，批量SRT、TXT

ChatTTS增强版V3来啦&#xff01;本次更新增加支持导入SRT、导入音色等功能。结合上次大家反馈的问题&#xff0c;修复了长文本、中英混读等问题。 项目已开源(https://github.com/CCmahua/ChatTTS-Enhanced) 项目介绍 V3 ChatTTS增强版V3&#xff0c;长文本修复&#xff0c…
阅读更多...
【职场人】职场进化记：我的“不惹人厌邀功精”之路

【职场人】职场进化记：我的“不惹人厌邀功精”之路

刚步入职场的我&#xff0c;就像一张白纸&#xff0c;什么都不懂&#xff0c;只知道埋头苦干。但渐渐地&#xff0c;我发现那些经常“冒泡”的同事似乎总能得到更多的关注和机会。我不禁想&#xff1a;“我是否也要成为那样一个‘邀功精’呢&#xff1f;” 不过&#xff0c;我…
阅读更多...
Go自定义数据的序列化流程

Go自定义数据的序列化流程

&#x1f49d;&#x1f49d;&#x1f49d;欢迎莅临我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;希望您在这里可以感受到一份轻松愉快的氛围&#xff0c;不仅可以获得有趣的内容和知识&#xff0c;也可以畅所欲言、分享您的想法和见解。 推荐:「stormsha的主页」…
阅读更多...
Apple - Launch Services Programming Guide

Apple - Launch Services Programming Guide

本文翻译整理自&#xff1a;Launch Services Programming Guide https://developer.apple.com/library/archive/documentation/Carbon/Conceptual/LaunchServicesConcepts/LSCIntro/LSCIntro.html#//apple_ref/doc/uid/TP30000999-CH201-TP1 文章目录 一、导言谁应该阅读此文档…
阅读更多...
Oracle基本语法（SQLPlus）

Oracle基本语法（SQLPlus）

目录&#xff1a; 前言&#xff1a; 准备工作&#xff1a; 登录&#xff1a; 1.打开SQL Plus命令行工具 第一种方式&#xff1a; 第二种方式&#xff1a; 2.以不同用户登录 SYSTEM&#xff08;普通管理员&#xff09;&#xff1a; SYS(超级管理员)&#xff1a; 不显示…
阅读更多...
二叉搜索树及其Java实现

二叉搜索树及其Java实现

二叉搜索树&#xff08;Binary Search Tree&#xff0c;简称BST&#xff09;是一种特殊的二叉树数据结构&#xff0c;它满足以下特性&#xff1a; 有序性&#xff1a;对于树中的任意一个节点&#xff0c;其左子树中所有节点的值都小于该节点的值&#xff0c;而其右子树中所有节…
阅读更多...
Web Worker 学习及使用

Web Worker 学习及使用

了解什么是 Web Worker 提供了可以在后台线程中运行 js 的方法。可以不占用主线程&#xff0c;不干扰用户界面&#xff0c;可以用来执行复杂、耗时的任务。 在worker中运行的是另一个全局上下文&#xff0c;不能直接获取 Window 全局对象。不同的 worker 可以分为专用和共享&…
阅读更多...
FreeCAD中事务机制实现原理分析

FreeCAD中事务机制实现原理分析

1.基本实现思路 实现一个文件的撤销重做最简单的思想就是&#xff0c;在每个撤销重做节点处保存一份文件的内容&#xff0c;撤销重做时&#xff0c;分别替换对应节点处的文件内容即可。这种做法开销太大&#xff0c;每个节点处都需要保存一份完整的文档内容&#xff0c;每次撤…
阅读更多...
fastapi+vue3+primeflex前后端分离开发项目第一个程序

fastapi+vue3+primeflex前后端分离开发项目第一个程序

安装axios axios是用来请求后端接口的。 https://www.axios-http.cn/docs/intro pnpm 是一个前端的包管理工具&#xff0c;当我们需要给前端项目添加新的依赖的时候&#xff0c;就可以使用pnpm install 命令进行安装。 pnpm install axios安装 primeflex primeflex是一个cs…
阅读更多...
十大经典排序算法——插入排序与希尔排序(超详解)

十大经典排序算法——插入排序与希尔排序(超详解)

一、插入排序 1.基本思想 直接插入排序是一种简单的插入排序法&#xff0c;基本思想是&#xff1a;把待排序的记录按其数值的大小逐个插入到一个已经排好序的有序序列中&#xff0c;直到所有的记录插入完为止&#xff0c;得到一个新的有序序列。 2.直接插入排序 当插入第 e…
阅读更多...
（八）ReactHooks使用规则

（八）ReactHooks使用规则

ReactHooks使用规则 只能在组件中或者其他自定义Hook函数中使用只能在组件的顶层调用&#xff0c;不能嵌套在if、for、其他函数中
阅读更多...
最新文章

Copyright @ 2022~2023