• ＜C++＞ 优先级队列

    目录

    前言

    一、priority_queue的使用

    1. 成员函数

    2. 例题

    二、仿函数

    三、模拟实现

    1.  迭代器区间构造函数 && AdjustDown

    2. pop

    3.  push && AdjustUp

    4. top

    5. size

    6. empty

     四、完整实现

    总结

    前言

            优先级队列以及前面的双端队列基本上已经脱离了队列定义，只是占了队列名字

    优先级队列——priority_queue

    1. 优先级队列是一种容器适配器，根据一些严格的弱排序标准，经过专门设计，其第一个元素始终是它所包含的最大元素。

    2. 此上下文类似于堆，其中元素可以随时插入，并且只能检索最大堆元素（优先级队列中顶部的元素）。

    3. 优先级队列作为容器适配器实现，容器适配器是使用特定容器类的封装对象作为其基础容器的类，提供一组特定的成员函数来访问其元素。元素从特定容器的“背面”弹出，这称为优先级队列的顶部。

    4. 底层容器可以是任何标准容器类模板，也可以是一些其他专门设计的容器类。容器应可通过随机访问迭代器访问，并支持以下操作：

    • empty（）
    • size（）
    • front（）
    • push_back（）
    • pop_back（）


    5. 标准容器类vector和deque满足这些要求。默认情况下，如果未为特定priority_queue类实例化指定容器类，则使用标准容器vector。

    6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。这是由容器适配器通过自动调用算法函数 make_heap、push_heap、pop_heap 自动完成的，并在需要时完成。

    注意：

    • priority_queue还是适配器，但是适配的是vector
    • 底层是二叉树的堆
    • priority_queue仍然包括在queue头文件中 
    • 默认大堆
    • Compare的缺省是less，表示的是大根堆

            可以使用仿函数修改为小根堆

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

    一、priority_queue的使用

    1. 成员函数

    2. 例题

    215. 数组中的第K个最大元素

    方法一：直接使用sort排序

    1. class Solution {
    2. public:
    3.     int findKthLargest(vector<int>& nums, int k) 
    4.     {
    5.         sort(nums.begin(), nums.end(), greater<int>());
    6.         return nums[k - 1];
    7.     }
    8. };

     方法二：优先级队列，建大堆

    1. class Solution {
    2. public:
    3.     int findKthLargest(vector<int>& nums, int k) 
    4.     {
    5.         priority_queue<int> pq(nums.begin(), nums.end());
    6.         while (--k)
    7.         {
    8.             pq.pop();
    9.         }
    10.         return pq.top();
    11.     }
    12. };

    方法三：维护一个有K个数据的小堆，遍历nums数组，若比top()值大，就入堆，最后返回top()数据

    1. class Solution {
    2. public:
    3.     int findKthLargest(vector<int>& nums, int k) 
    4.     {
    5.         priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.begin() + k);
    6.         for (int i = k; i < nums.size(); ++i)
    7.         {
    8.             if (nums[i] > pq.top())
    9.             {
    10.                 pq.pop();
    11.                 pq.push(nums[i]);
    12.             }
    13.         }
    14.  
    15.         return pq.top();
    16.         
    17.     }
    18. };

    注意：

            sort函数最后一个参数是greater()，是一个匿名对象，而在priority_queue<>内部，第三个模板是greater，是类型，不能加括号

    二、仿函数

            我们在之前就遇到过sort函数如果想实现降序，需要加上仿函数greater<类型>()，那么什么是仿函数呢？它又有什么作用？

    我们来看一个简单的例子：

    1. class Fun
    2. {
    3. public:
    4. 	bool operator()(int a, int b)
    5. 	{
    6. 		return a < b;
    7. 	}
    8. };
    9.  
    10. int main()
    11. {     
    12.     Fun func;
    13.     cout << func(1, 2) << endl;
    14.     //等价于
    15.     cout << func.operator()(1, 2) << endl;
    16.  
    17.     return 0;
    18. }
    • 这里的Fun就是仿函数，由Fun类定义的对象称为函数对象
    • 仿函数，顾名思义，一个类的对象可以像函数一样使用，它替代了c语言里的函数指针，我们只需要重载 () 符号，就可以像使用函数一样调用它的 () 运算符重载函数

    那么这样的仿函数有什么作用呢？

    •  替代c语言的函数指针，因为c语言的函数指针很复杂、容易出错
    • 搭配模板可以实现多类型的函数运算，不会将函数“写死”，例如：我们写Less、Greater类，重载（）符号，在需要的地方实例化函数对象，如果有比较大小的情况就使用函数对象（参数1，参数2），原理就是调用operator()函数，像函数一样调用

    下面是priority_queue带上第三个模板参数Less后使用仿函数的代码：

    1. template<class T>
    2. class Less
    3. {
    4. public:
    5. 	bool operator()(const T& a, const T& b)
    6. 	{
    7. 		return a < b;
    8. 	}
    9. };
    10.  
    11. template<class T>
    12. class Greater
    13. {
    14. public:
    15. 	bool operator()(const T& a, const T& b)
    16. 	{
    17. 		return a > b;
    18. 	}
    19. };
    20.  
    21. namespace my_priority_queue
    22. {
    23. 	// Less 才是Less类的类型
    24. 	template<class T, class Container = vector, class Compare = Less>
    25. 	class priority_queue
    26. 	{
    27. 	private:
    28. 		//大堆，向下调整
    29. 		void AdjustDown(int parent)
    30. 		{
    31. 			//创建函数对象，Less模板类型就是<比较，Greater模板类型就是>比较
    32. 			Compare com;
    33.  
    34. 			//找左右孩子中最大的哪一个
    35. 			int child = parent * 2 + 1;
    36. 			while (child < _con.size())
    37. 			{
    38. 				//因为com是比较小于关系，所以需要将原先大于的表达式逆一下
    39. 				
    40. 				//判断右孩子是否存在
    41. 				/*if (child + 1 < _con.size() && _con[child + 1] > _con[child])*/
    42. 				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
    43. 				{
    44. 					++child;
    45. 				}
    46.  
    47. 				//if (_con[child] > _con[parent])
    48. 				if (com(_con[parent], _con[child]))
    49. 				{
    50. 					swap(_con[parent], _con[child]);
    51. 					parent = child;
    52. 					child = parent * 2 + 1;
    53. 				}
    54. 				else
    55. 				{
    56. 					break;
    57. 				}
    58. 			}
    59.  
    60. 		}
    61.  
    62. 		void AdjustUp(int child)
    63. 		{
    64. 			Compare com;
    65.  
    66. 			int parent = (child - 1) / 2;
    67. 			while (child > 0)	//最坏情况：孩子等于0时结束
    68. 			{
    69. 				if (com(_con[parent], _con[child]))
    70. 				{
    71. 					swap(_con[parent], _con[child]);
    72. 					child = parent;
    73. 					parent = child - 1 >> 1;
    74. 				}
    75. 				else
    76. 				{
    77. 					break;
    78. 				}
    79. 			}
    80. 		}
    81.  
    82. 	public:
    83. 		template<class InputIterator>	//input只写迭代器
    84.  
    85. 		//迭代器区间构造函数
    86. 		priority_queue(InputIterator first, InputIterator last)
    87. 		{
    88. 			while (first != last)
    89. 			{
    90. 				_con.push_back(*first);
    91. 				++first;
    92. 			}
    93.  
    94. 			//建堆
    95. 			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i )
    96. 			{
    97. 				AdjustDown(i);
    98. 			}
    99. 		}
    100.  
    101. 		void pop()
    102. 		{
    103. 			//交换后，尾删，并向下调整
    104. 			swap(_con[0], _con[_con.size() - 1]);
    105. 			_con.pop_back();
    106. 			AdjustDown(0);
    107. 		}
    108.  
    109. 		void push(const T& x)
    110. 		{
    111. 			_con.push_back(x);
    112. 			AdjustUp(_con.size() - 1);
    113. 		}
    114.  
    115. 	private:
    116. 		//容器
    117. 		Container _con;
    118. 	};
    119. }

            如果比较的类型是其他自定义类型，并且该类没有重载operator<函数，那么我们就需要手写一个仿函数进行比较，否则编译错误，无法进行比较

           因为库里的仿函数使用了模板，是什么类型就按什么类型相比，那么如果是new返回的指针类型，由于每次new返回的地址相当于是随机的，又比较的是指针类型的大小，所以比较结果也是随机结果。所以我们还是需要写仿函数，修改比较方式，去比较指针指向的内容即可。

    三、模拟实现

    编译错误，找不到出错位置怎么办？

            如果代码编译错误，找不到在哪，那么逐步屏蔽掉一些代码，逐步排查，是十分有效的找到错误处方法

            priority_queue也同queue、stack一样，是适配器，适配vector容器

    1.  迭代器区间构造函数 && AdjustDown

    • 采用封装容器vector的push_back尾插数据，因为默认是大堆，向下建堆，所以尾插数据后，将从最后一个元素的父亲结点—— (_con.size() - 1 - 1) / 2 开始向下调整。
    • 向下调整函数不用多说，在二叉树部分我们详细讲解过
    1. namespace my_priority_queue
    2. {
    3. 	// Less 才是Less类的类型
    4. 	template<class T, class Container = vector, class Compare = Less>
    5. 	class priority_queue
    6. 	{
    7. 	private:
    8. 		//大堆，向下调整
    9. 		void AdjustDown(int parent)
    10. 		{
    11. 			//创建函数对象，Less模板类型就是<比较，Greater模板类型就是>比较
    12. 			Compare com;
    13.  
    14. 			//找左右孩子中最大的哪一个
    15. 			int child = parent * 2 + 1;
    16. 			while (child < _con.size())
    17. 			{
    18. 				//因为com是比较小于关系，所以需要将原先大于的表达式逆一下
    19. 				
    20. 				//判断右孩子是否存在
    21. 				/*if (child + 1 < _con.size() && _con[child + 1] > _con[child])*/
    22. 				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
    23. 				{
    24. 					++child;
    25. 				}
    26.  
    27. 				//if (_con[child] > _con[parent])
    28. 				if (com(_con[parent], _con[child]))
    29. 				{
    30. 					swap(_con[parent], _con[child]);
    31. 					parent = child;
    32. 					child = parent * 2 + 1;
    33. 				}
    34. 				else
    35. 				{
    36. 					break;
    37. 				}
    38. 			}
    39.  
    40. 		}
    41.  
    42. 	public:
    43. 		template<class InputIterator>	//input只写迭代器
    44.  
    45. 		//迭代器区间构造函数
    46. 		priority_queue(InputIterator first, InputIterator last)
    47. 		{
    48. 			while (first != last)
    49. 			{
    50. 				_con.push_back(*first);
    51. 				++first;
    52. 			}
    53.  
    54. 			//建堆
    55. 			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i )
    56. 			{
    57. 				AdjustDown(i);
    58. 			}
    59. 		}
    60.  
    61.  
    62. 	private:
    63. 		//容器
    64. 		Container _con;
    65. 	};
    66. }

     2. pop

    • 堆的pop，将堆顶数据与最后一个数据进行交换，再进行pop_back，再将堆顶数据向下调整
    1. 		void pop()
    2. 		{
    3. 			//交换后，尾删，并向下调整
    4. 			swap(_con[0], _con[_con.size() - 1]);
    5. 			_con.pop_back();
    6.  
    7. 			AdjustDown(0);
    8. 		}

     3.  push && AdjustUp

    • 尾插数据后，将该数据向上调整
    1. 		void AdjustUp(int child)
    2. 		{
    3. 			Compare com;
    4.  
    5. 			int parent = (child - 1) / 2;
    6. 			while (child > 0)	//最坏情况：孩子等于0时结束
    7. 			{
    8. 				if (com(_con[parent], _con[child]))
    9. 				{
    10. 					swap(_con[parent], _con[child]);
    11. 					child = parent;
    12. 					parent = child - 1 >> 1;
    13. 				}
    14. 				else
    15. 				{
    16. 					break;
    17. 				}
    18. 			}
    19. 		}
    20.  
    21. 		void push(const T& x)
    22. 		{
    23. 			_con.push_back(x);
    24. 			AdjustUp(_con.size() - 1);
    25. 		}

     4. top

    • 返回堆顶数据，返回值是 const T&
    1. 		const T& top()
    2. 		{
    3. 			return _con[0];
    4. 		}

     5. size

    • 返回vector的size()即可
    1. 		size_t size()
    2. 		{
    3. 			return _con.size();
    4. 		}

     6. empty

    • 直接调用vector的empty函数即可
    1. 		size_t size()
    2. 		{
    3. 			return _con.size();
    4. 		}

     四、完整实现

    1. #pragma once
    2. #include
    3. #include
    4. #include
    5. using namespace std;
    6.  
    7. template<class T>
    8. class Less
    9. {
    10. public:
    11. 	bool operator()(const T& a, const T& b)
    12. 	{
    13. 		return a < b;
    14. 	}
    15. };
    16.  
    17. template<class T>
    18. class Greater
    19. {
    20. public:
    21. 	bool operator()(const T& a, const T& b)
    22. 	{
    23. 		return a > b;
    24. 	}
    25. };
    26.  
    27. namespace my_priority_queue
    28. {
    29. 	// Less 才是Less类的类型
    30. 	template<class T, class Container = vector, class Compare = Less>
    31. 	class priority_queue
    32. 	{
    33. 	private:
    34. 		//大堆，向下调整
    35. 		void AdjustDown(int parent)
    36. 		{
    37. 			//创建函数对象，Less模板类型就是<比较，Greater模板类型就是>比较
    38. 			Compare com;
    39.  
    40. 			//找左右孩子中最大的哪一个
    41. 			int child = parent * 2 + 1;
    42. 			while (child < _con.size())
    43. 			{
    44. 				//因为com是比较小于关系，所以需要将原先大于的表达式逆一下
    45. 				
    46. 				//判断右孩子是否存在
    47. 				/*if (child + 1 < _con.size() && _con[child + 1] > _con[child])*/
    48. 				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
    49. 				{
    50. 					++child;
    51. 				}
    52.  
    53. 				//if (_con[child] > _con[parent])
    54. 				if (com(_con[parent], _con[child]))
    55. 				{
    56. 					swap(_con[parent], _con[child]);
    57. 					parent = child;
    58. 					child = parent * 2 + 1;
    59. 				}
    60. 				else
    61. 				{
    62. 					break;
    63. 				}
    64. 			}
    65.  
    66. 		}
    67.  
    68. 		void AdjustUp(int child)
    69. 		{
    70. 			Compare com;
    71.  
    72. 			int parent = (child - 1) / 2;
    73. 			while (child > 0)	//最坏情况：孩子等于0时结束
    74. 			{
    75. 				if (com(_con[parent], _con[child]))
    76. 				{
    77. 					swap(_con[parent], _con[child]);
    78. 					child = parent;
    79. 					parent = child - 1 >> 1;
    80. 				}
    81. 				else
    82. 				{
    83. 					break;
    84. 				}
    85. 			}
    86. 		}
    87.  
    88. 	public:
    89.  
    90. 		priority_queue()
    91. 		{}
    92.  
    93. 		//迭代器区间构造函数
    94. 		template<class InputIterator>	//input只写迭代器
    95. 		priority_queue(InputIterator first, InputIterator last)
    96. 		{
    97. 			while (first != last)
    98. 			{
    99. 				_con.push_back(*first);
    100. 				++first;
    101. 			}
    102.  
    103. 			//建堆
    104. 			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i )
    105. 			{
    106. 				AdjustDown(i);
    107. 			}
    108. 		}
    109.  
    110. 		void pop()
    111. 		{
    112. 			//交换后，尾删，并向下调整
    113. 			swap(_con[0], _con[_con.size() - 1]);
    114. 			_con.pop_back();
    115.  
    116. 			AdjustDown(0);
    117. 		}
    118.  
    119. 		void push(const T& x)
    120. 		{
    121. 			_con.push_back(x);
    122.  
    123. 			AdjustUp(_con.size() - 1);
    124. 		}
    125.  
    126. 		const T& top()
    127. 		{
    128. 			return _con[0];
    129. 		}
    130.  
    131. 		size_t size()
    132. 		{
    133. 			return _con.size();
    134. 		}
    135.  
    136. 		bool empty()
    137. 		{
    138. 			return _con.empty();
    139. 		}
    140.  
    141. 	private:
    142. 		//容器
    143. 		Container _con;
    144. 	};
    145. }
    146.  
    147. void test_priority_queue1()
    148. {
    149. 	// 默认是大堆 -- less
    150. 	//priority_queue pq;
    151.  
    152. 	// 仿函数控制实现小堆
    153. 	my_priority_queue::priority_queue<int, vector<int>, Greater<int>> pq;
    154.  
    155. 	pq.push(3);
    156. 	pq.push(5);
    157. 	pq.push(1);
    158. 	pq.push(4);
    159.  
    160. 	while (!pq.empty())
    161. 	{
    162. 		cout << pq.top() << " ";
    163. 		pq.pop();
    164. 	}
    165. 	cout << endl;
    166. }

    总结

            priority_queue优先级队列就是存储在vector内的堆，掌握向上向下调整函数，可以回顾之前的文章堆的实现一节。

            最后，如果小帅的本文哪里有错误，还请大家指出，请在评论区留言（ps：抱大佬的腿），新手创作，实属不易，如果满意，还请给个免费的赞，三连也不是不可以（流口水幻想）嘿！那我们下期再见喽，拜拜！

  • 相关阅读:
    第一章 概述
    Vue3+TypeScript学习
    STM32-14-FSMC_LCD
    [附源码]java毕业设计校园拓展活动管理系统
    Grandle安装配置使用
    深入理解通知服务NotificationListenerService原理
    linux操作命令
    常用软件静默安装参数
    使用Oracle自带SqlPlus导入导出数据库脚本
    基于SSM框架的民宿预订系统的设计与实现毕业设计源码281118
  • 原文地址：https://blog.csdn.net/prodigy623/article/details/134358565