【C++入门到精通】C++入门 —— priority_queue(STL)优先队列

这篇具有很好参考价值的文章主要介绍了【C++入门到精通】C++入门 —— priority_queue(STL)优先队列。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

【C++入门到精通】C++入门 —— priority_queue(STL)优先队列,c++,开发语言

前言

⭕文章绑定了VS平台下std::priority_queue的源码,大家可以下载了解一下😍

前面我们讲了C语言的基础知识,也了解了一些数据结构,并且讲了有关C++的命名空间的一些知识点以及关于C++的缺省参数、函数重载,引用 和 内联函数也认识了什么是类和对象以及怎么去new一个 ‘对象’ ,以及学习了几个STL的结构也相信大家都掌握的不错,接下来博主将会带领大家继续学习有关C++比较重要的知识点—— priority_queue(STL)优先队列。下面话不多说坐稳扶好咱们要开车了😍

一、priority_queue简介

⭕官方文档
【C++入门到精通】C++入门 —— priority_queue(STL)优先队列,c++,开发语言

1. 概念

priority_queue是C++标准库中的一个容器适配器(container adapter),用于实现优先队列(priority queue)的数据结构。优先队列是一种特殊的队列,其中的元素按照一定的优先级进行排序,每次取出的元素都是优先级最高的。它的底层实现通常使用堆(heap)数据结构。

在C++中,priority_queue模板类定义在<queue>头文件中,可以通过指定元素类型和比较函数来创建不同类型的优先队列。比较函数用于确定元素的优先级,可以是函数指针、函数对象或Lambda表达式。

⭕需要注意的是,默认情况下,priority_queue使用std::less作为比较函数,即元素的优先级按照从大到小的顺序排列。如果需要按照从小到大的顺序排列,可以使用std::greater作为比较函数。

2. 特点

  1. 优先级排序:priority_queue中的元素按照一定的优先级进行排序。默认情况下,元素的优先级按照从大到小的顺序排列,也可以通过自定义的比较函数来指定不同的排序方式。

  2. 自动排序:在插入元素时,priority_queue会根据元素的优先级自动进行排序。每次插入新元素时,都会将新元素放置在正确的位置上。

  3. 取出优先级最高元素:priority_queue提供了一种方便的方式来取出优先级最高的元素。使用top()函数可以访问优先级最高的元素,而使用pop()函数可以将该元素从队列中移除。

  4. 底层实现采用堆:priority_queue通常使用堆(heap)数据结构来实现。堆是一种具有特定性质的二叉树,可以高效地插入新元素和取出优先级最高的元素。

  5. 动态大小:priority_queue的大小可以根据需要进行动态调整。可以随时插入新元素和删除已有元素,并在必要时自动重新排序。

⭕需要注意的是,priority_queue并不支持直接访问和修改除了优先级最高元素外的其他元素。如果需要对特定元素进行操作,通常需要先将其取出,然后再进行操作,最后再将其放回优先队列中。

二、priority_queue使用

1. 基本操作

  1. 包含头文件:首先,在使用priority_queue之前,你需要包含<queue>头文件。
#include <queue>
  1. 定义容器和比较函数:然后,你需要定义一个priority_queue对象,并指定元素类型和可选的比较函数(默认为std::less)。
std::priority_queue<int, std::vector<int>, std::less<int>> pq;

上面的示例定义了一个存储整数的优先队列,使用std::less作为比较函数,以便元素按照从大到小的顺序排列。

  1. 插入元素:你可以使用push()函数插入元素到priority_queue中。插入的元素会根据其优先级自动进行排序。
pq.push(3);
pq.push(1);
pq.push(4);
pq.push(1);

在上面的示例中,我们依次插入了4个整数到优先队列中。

  1. 访问和移除元素:你可以使用top()函数访问优先级最高的元素,使用pop()函数移除优先级最高的元素。
std::cout << pq.top() << std::endl;  // 访问优先级最高的元素
pq.pop();                           // 移除优先级最高的元素

在上面的示例中,我们先输出了优先级最高的元素,然后将其从队列中移除。

  1. 检查队列是否为空:你可以使用empty()函数来检查priority_queue是否为空。
if (pq.empty()) {
    // 队列为空
} else {
    // 队列不为空
}

下面的代码,演示了如何使用priority_queue

#include <queue>
#include <iostream>

int main() {
    std::priority_queue<int, std::vector<int>, std::less<int>> pq;

    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(1);

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

    return 0;
}

输出结果为:4 3 1 1

在上面的代码中,我们创建了一个存储整数的优先队列pq,并依次插入了4个元素。然后,我们使用top()函数和pop()函数访问和移除元素,最后使用empty()函数检查队列是否为空。

2. 底层结构

priority_queue的底层通常使用堆(heap)数据结构来实现。堆是一种二叉树的数据结构(堆,数据结构详细介绍链接),具有以下特点:

  1. 堆结构是一个完全二叉树(Complete Binary Tree),即除了最后一层外,其他层都必须是满的,且最后一层的结点都靠左排列。

  2. 二叉堆分为最大堆(Max Heap)和最小堆(Min Heap)两种类型。

    • 最大堆:每个父节点的值都大于或等于其子节点的值,即根节点的值最大。
    • 最小堆:每个父节点的值都小于或等于其子节点的值,即根节点的值最小。

priority_queue中,默认情况下采用最大堆实现,即优先级最高的元素存储在根节点,根节点的值最大。根据堆的性质,保证了在插入元素时,优先队列会根据元素的优先级进行自动排序,并在取出元素时能够取出优先级最高的元素。
【C++入门到精通】C++入门 —— priority_queue(STL)优先队列,c++,开发语言

三、priority_queue模拟实现

⭕ C++代码

#pragma once
#include<iostream>
using namespace std;
#include<vector>
namespace yws
{
	template<class T, class Container = vector<T>, class Compare = std::less<T>>
	class priority_queue
	{
	public:
		priority_queue()
		{}
		template <class Inputinterpreator>
		priority_queue(Inputinterpreator first, Inputinterpreator last)
		{
			while (first != last)
			{
				_con.push_back(*first);
				++first;
			}
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
			{
				adjust_down(i);
			}
		}
		void adjust_up(size_t child)
		{
			Compare com;
			size_t parent = (child - 1) / 2;
			while (child > 0)
			{
				if (com(_con[parent], _con[child]))
				{
					std::swap(_con[child], _con[parent]);
				}
				else
				{
					break;
				}
				child = parent;
				parent = (child - 1) / 2;
			}
		}
		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 = child + 1;
				}
				if (com(_con[parent], _con[child]))
				{
					std::swap(_con[parent], _con[child]);
				}
				else
				{
					break;
				}
				parent = child;
				child = (parent * 2) + 1;
			}
		}
		void pop()
		{
			std::swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();

			adjust_down(0);
		}
		const T& top()
		{
			return _con[0];
		}
		bool empty()  const
		{
			return _con.empty();
		}
		size_t size() const
		{
			return _con.size();
		}

	private:
		Container _con;
	};
}

⭕priority_queue中的仿函数

priority_queue中,仿函数用于比较元素的优先级,并根据其返回值确定它们在队列中的位置。默认情况下,priority_queue使用std::less作为仿函数,也就是将元素按照从大到小的顺序进行排序

你可以使用不同的仿函数来改变元素的排序方式。以下是一些常见的仿函数:

  • std::less<T>:对于基本数据类型和自定义类型,默认使用<运算符进行比较,按照从大到小的顺序排序。
  • std::greater<T>:对于基本数据类型和自定义类型,默认使用>运算符进行比较,按照从小到大的顺序排序。

除了上述默认提供的仿函数外,你还可以自定义仿函数来实现自定义的元素比较规则。自定义仿函数需要满足严格弱排序(Strict Weak Ordering)的要求,即:

  • 比较关系必须是可传递的(transitive):对于任意元素a、b和c,如果a与b比较相等,b与c比较相等,则a与c比较也相等。
  • 比较关系不能是部分顺序(partial order):对于任意元素a和b,它们不能同时大于、小于或等于彼此。
  • 比较关系必须是可比较的(comparable):比较关系的结果必须对所有元素定义明确的大小关系。

以下这段代码,演示了如何自定义一个仿函数来实现元素的自定义排序方式:

#include <iostream>
#include <queue>
#include <functional>

struct Person {
    std::string name;
    int age;

    Person(const std::string& n, int a) : name(n), age(a) {}
};

// 自定义仿函数
struct CompareByAge {
    bool operator()(const Person& p1, const Person& p2) const {
        return p1.age > p2.age;  // 按照年龄从小到大排序
    }
};

int main() {
    std::priority_queue<Person, std::vector<Person>, CompareByAge> pq;

    pq.push(Person("Alice", 25));
    pq.push(Person("Bob", 30));
    pq.push(Person("Charlie", 20));

    while (!pq.empty()) {
        Person p = pq.top();
        pq.pop();
        std::cout << p.name << " - " << p.age << std::endl;
    }

    return 0;
}

输出结果为:

Charlie - 20
Alice - 25
Bob - 30

在上面的代码中,我们定义了一个名为CompareByAge的结构体,重载了函数调用运算符operator(),按照Person对象的age成员进行比较。然后,我们将CompareByAge作为优先队列的仿函数类型,并插入3个Person对象到优先队列中。最后,我们按照自定义的排序方式依次取出元素并输出。

总结

优先队列是一种特殊的队列,其中存储的元素按照一定的优先级进行排列。在priority_queue中,优先级最高的元素能够快速被访问和删除。

首先,我们介绍了priority_queue的概念和特点。它是基于堆(heap)这种数据结构实现的,通常使用最大堆来进行内部排序。最大堆保证了根节点的值最大,并且任意节点的值大于或等于其子节点的值。这种特性使得优先队列能够高效地访问和删除具有最高优先级的元素。

接着,我们深入探讨了priority_queue的使用方法。基本操作包括插入元素、删除元素、访问元素和检查队列是否为空。

底层结构是priority_queue的关键部分,它通常使用堆来实现。在堆中,通过使用数组的索引来表示节点之间的关系,能够快速定位和操作元素

最后,我们探讨了在priority_queue中使用的仿函数。仿函数用于确定元素之间的优先级,决定元素在队列中的位置。默认情况下,priority_queue使用std::less仿函数进行比较,对元素进行降序排列。你还可以选择其他仿函数或自定义仿函数来实现不同的排序方式。

温馨提示

感谢您对博主文章的关注与支持!在阅读本篇文章的同时,可以留下您宝贵的意见和反馈。如果您喜欢这篇文章,可以点赞、评论和分享给您的同学,这将对我提供巨大的鼓励和支持。另外,我计划在未来的更新中持续探讨与本文相关的内容。我会为您带来更多关于C++以及编程技术问题的深入解析、应用案例和趣味玩法等。请继续关注博主的更新,不要错过任何精彩内容!

再次感谢您的支持和关注。期待与您建立更紧密的互动,共同探索C++、算法和编程的奥秘。祝您生活愉快,排便顺畅!
【C++入门到精通】C++入门 —— priority_queue(STL)优先队列,c++,开发语言文章来源地址https://www.toymoban.com/news/detail-663578.html

到了这里,关于【C++入门到精通】C++入门 —— priority_queue(STL)优先队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • C++优先队列(priority_queue)详解

    目录 一、 定义 二、优先队列内元素访问 三、优先队列常用函数 四、优先队列内元素的优先级          优先队列(priority_queue),底层的数据结构为 堆(heap) ,以此 保证队首元素一定是当前队列所有元素中优先级最高的。 我们也可以随时往优先队里面加入(push)元素,其队

    2024年02月16日
    浏览(42)
  • 【STL】priority_queue(优先级队列)详解及仿函数使用(附完整源码)

    1. priority_queue介绍和使用 1.1 priority_queue介绍 优先级队列也是在 queue 里: 因此和 queue 一样, priority_queue 也是一个容器适配器。priority_queue官方文档 优先队列是一种容器适配器,根据严格的弱排序标准,它的第一个元素总是它所包含的元素中最大的。 类似于堆,在堆中可以随

    2024年02月08日
    浏览(42)
  • C++中的优先队列(priority_queue)

    什么是优先队列 优先队列(priority queue) 普通的队列是一种先进先出的数据结构,元素在队列尾追加,而从队列头删除。在优先队列中,元素被赋予优先级。当访问元素时,具有最高优先级的元素最先删除。优先队列具有优先级最高先出的性质。通常采用堆数据结构来实现。

    2024年02月15日
    浏览(47)
  • C++ 优先队列 priority_queue 使用篇

    目录 1.储备知识    (1)数据结构:堆   (2)仿函数(函数对象)     [1]理解仿函数     [2]实现仿函数   (3)priority_queue理解     [1]什么是priority_queue (优先队列)?     [2]优先队列性质 2.priority_queue的参数理解(重要!!!)   (1)priority_queue的参数     [1]priority_queue类模板参数     [

    2024年03月12日
    浏览(83)
  • 【C++初阶】模拟实现优先级队列priority_queue

    👦个人主页:@Weraphael ✍🏻作者简介:目前学习C++和算法 ✈️专栏:C++航路 🐋 希望大家多多支持,咱一起进步!😁 如果文章对你有帮助的话 欢迎 评论💬 点赞👍🏻 收藏 📂 加关注✨ 优先级队列顾名思义就是 按优先级出队列 priority_queue 是一个容器适配器,默认使用

    2024年02月10日
    浏览(40)
  • 【C++】详解priority_queue(优先级队列)与函数对象

    目录 一、priority_queue 的介绍和使用 1.1priority_queue 的介绍 2.2priority_queue 的使用 二、仿函数 2.1什么是仿函数 2.2仿函数的作用 三、函数对象的特点(知识点多) 3.1分析特点5(比较普通函数与函数对象) 3.1.1利用普通函数传递参数 拓展之:深度剖析函数利用模板的本质 3.1.2利用

    2024年02月08日
    浏览(40)
  • C++——优先级队列(priority_queue)的使用及实现

    目录 一.priority_queue的使用 1.1、基本介绍 1.2、优先级队列的定义 1.3、基本操作(常见接口的使用) 1.4、重写仿函数支持自定义数据类型 二.priority_queue的模拟实现 2.1、构造重要的调整算法 2.2、常见接口的实现 push() pop() top() empty()、size()  三.利用仿函数改进调整算法 我们之前

    2024年02月02日
    浏览(43)
  • 【C++】——栈和队列(stack、queue)及优先队列(priority_queue)的介绍和模拟实现

    今天我们来学习C++stl六大组件的其中一种,容器适配器,stack、queue及priority_queue都是容器适配器。我们循序渐进,接下来让我们先认识一下什么是容器适配器。 适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结),该

    2024年02月08日
    浏览(51)
  • 【C++航海王:追寻罗杰的编程之路】priority_queue(优先队列) | 容器适配器你知道哪些?

    目录 1 - priority_queue的介绍和使用 1.1 - priority_queue的介绍 1.2 - priority_queue的使用 1.3 - priority_queue的模拟实现 2 - 容器适配器 2.1 - 什么是适配器 2.2 - STL标准库中stack和queue的底层结构 2.3 - deque的介绍 2.3.1 - deque的原理介绍 2.3.2 - deque的缺陷 2.4 - 为什么选择deque作为stack和queue的底

    2024年04月10日
    浏览(46)
  • 优先级队列priority_queue

    关于less建大根堆,输出降序序列,greater建小根堆,输出升序序列,这点和sort()函数相反,参考我的这篇博客 底层原理 priority_queue底层维护着一个对应类型的,vector物理结构,但相当于堆排序的结构,这个vector逻辑结构是一个二叉堆; 每次 插入数据 ,我们插在堆尾(vector尾),

    2024年02月16日
    浏览(40)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包