【C++入门到精通】C++入门 —— priority

阅读导航

• 前言
• 一、priority_queue简介
• • 1. 概念
  • 2. 特点
  • 二、priority_queue使用
  • • 1. 基本操作
    • 2. 底层结构
    • 三、priority_queue模拟实现
    • • ⭕ C++代码
      • ⭕priority_queue中的仿函数
      • 总结
      • 温馨提示

        前言

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

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

        一、priority_queue简介

        ⭕官方文档

        

        1. 概念

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

        在C++中，priority_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之前，你需要包含头文件。

        #include 
        

        1. 定义容器和比较函数：然后，你需要定义一个priority_queue对象，并指定元素类型和可选的比较函数（默认为std::less）。

        std::priority_queue 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 
            // 队列为空
        } else {
            // 队列不为空
        }
        
            std::priority_queue
                std::cout 
        	template
        	public:
        		priority_queue()
        		{}
        		template 
        			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