1. Toy模板网首页
  2. > Toy博客

[C++]priority_queue的介绍及模拟实现

9月前 作者：EnticE152 分类：Toy博客 阅读(42) 违法举报

这篇具有很好参考价值的文章主要介绍了[C++]priority_queue的介绍及模拟实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

目录

priority_queue的介绍及模拟实现：：

                                                        priority_queue的介绍

                                                        priority_queue的定义方式

                                                        priority_queue各个接口的使用

                                                        堆的向上调整算法

                                                        堆的向下调整算法

                                                        仿函数

                                                        priority_queue的模拟实现

                                                        反向迭代器的底层原理

                                                        反向迭代器的模拟实现

priority_queue的介绍及模拟实现：：

priority_queue的介绍

优先级队列默认使用vector作为其底层存储数据的容器，在vector上又使用了堆的向上调整和向下调整算法将vector中的元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。

[C++]priority_queue的介绍及模拟实现,c++,开发语言

#include <queue>
int main()
{
	priority_queue<int> pq;
	pq.push(3);
	pq.push(1);
	pq.push(2);
	pq.push(5);
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;
	return 0;
}

[C++]priority_queue的介绍及模拟实现,c++,开发语言

#include <functional>
#include <queue>
int main()
{
	priority_queue<int,vector<int>,greater<int>> pq;
	pq.push(3);
	pq.push(1);
	pq.push(2);
	pq.push(5);
	while (!pq.empty())
	{
		cout << pq.top() << " ";
		pq.pop();
	}
	cout << endl;
	return 0;
}

[C++]priority_queue的介绍及模拟实现,c++,开发语言

priority_queue的定义方式

方式一：使用vector作为底层容器，内部构造大堆结构

priority_queue<int,vector<int>,less<int>> pq1;

方式二：使用vector作为底层容器，内部构造小堆结构

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

方式三：不指定底层容器，默认为大堆结构

priority_queue<int> pq3;

priority_queue各个接口的使用

成员函数 功能
push 插入元素到队尾并调整为堆结构
pop 弹出堆顶元素
top 访问堆顶元素
size 获取队列中有效元素个数
empty 判断队列是否为空
swap 交换两个队列的内容

priority_queueOJ：数组中第K大的元素

[C++]priority_queue的介绍及模拟实现,c++,开发语言

//方法一:建大堆 再popK次
class Solution 
{
public:
	int findKthLargest(vector<int>& nums, int k) 
	{
		priority_queue<int> pq(nums.begin(), nums.end());
		while (--k)
		{
			pq.pop();
		}
		return pq.top();
	}
};
//方法二:建K个数的小堆 和堆顶数据比较
class Solution
{
public:
	int findKthLargest(vector<int>& nums, int k)
	{
		priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.begin() + k);
		for (size_t i = k; i < nums.size(); ++i)
		{
			if (nums[i] > pq.top())
			{
				pq.pop();
				pq.push(nums[i]);
			}
		}
		return pq.top();
	}
};

堆的向上调整算法

思想：

1.将目标结点与父结点进行比较

2.若目标结点的值比父节点的值大，则交换目标结点与其父节点的位置，并将原目标节点的父节点当作新的目标节点继续进行向上调整，若目标节点的值比其父节点的值小，则停止向上调整。

void AdjustUp(vector<int>& v, size_t child)
{
	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
		if (v[child] > v[parent])
		{
			swap(v[child], v[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

堆的向下调整算法

思想：

1.将目标节点与其较大的子节点进行比较

2.若目标节点的值比其较大的子节点的值小，则交换目标节点与其较大的子节点的位置，并将原目标节点的较大子节点当作新的目标节点继续进行向下调整，若目标节点的值比其较大子节点的值大，则停止向下调整。

void AdjustDown(vector<int>& v, int n , size_t parent)
{
	size_t child = 2 * parent + 1;
	while (child < v.size())
	{
		if (child + 1 < n && v[child] < v[child + 1])
		{
			++child;
		}
		if (v[parent] < v[child])
		{
			std::swap(v[child], v[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

仿函数

仿函数的介绍：

namespace wjq
{
	template <class T>
	struct less
	{
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};

	template <class T>
	struct greater
	{
		bool operator()(const T& x, const T& y)
		{
			return x > y;
		}
	};
}
int main()
{
	wjq::less<int> lessFunc;
	lessFunc(1, 2);
	return 0;
}

[C++]priority_queue的介绍及模拟实现,c++,开发语言

仿函数的使用场景：

bool cmp(int x, int y)
{
	return y > x;
}
void BubbleSort(int* a, int n, bool(*pcom)(int, int))
{
	for (int i = 0; i < n; i++)
	{
		int exchange = 0;
		for (int j = 1; j < n - i; j++)
		{
			if (pcom(a[j - 1] , a[j]))
			{
				std::swap(a[j - 1], a[j]);
				exchange = 1;
			}
		}
		if (exchange == 0)
		{
			break;
		}
	}
}
int main()
{
	int a[] = { 2,3,4,5,6,1,4,9 };
	BubbleSort(a, 8, cmp);
	for (size_t i = 0; i < 8; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
	return 0;
}

[C++]priority_queue的介绍及模拟实现,c++,开发语言

namespace wjq
{
	template <class T>
	struct less
	{
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};

	template <class T>
	struct greater
	{
		bool operator()(const T& x, const T& y)
		{
			return x > y;
		}
	};
}
template<class T,class Compare>
void BubbleSort(T* a, int n, Compare com)
{
	for (int i = 0; i < n; i++)
	{
		int exchange = 0;
		for (int j = 1; j < n - i; j++)
		{
			if (com(a[j], a[j - 1]))
			{
				std::swap(a[j - 1], a[j]);
				exchange = 1;
			}
		}
		if (exchange == 0)
		{
			break;
		}
	}
}
int main()
{
	wjq::less<int> lessFunc;
	int a[] = { 2,3,4,5,6,1,4,9 };
	BubbleSort(a, 8, lessFunc);
	for (size_t i = 0; i < 8; i++)
	{
		cout << a[i] << " ";
	}
	cout << endl;
	return 0;
}

[C++]priority_queue的介绍及模拟实现,c++,开发语言

[C++]priority_queue的介绍及模拟实现,c++,开发语言

[C++]priority_queue的介绍及模拟实现,c++,开发语言

仿函数的特殊使用场景：

如果在priority_queue中放自定义类型的数据，用户需要自己提供>和<的重载

class Date
{
public:
	Date(int year = 1900, int month = 1, int day = 1)
		: _year(year)
		, _month(month)
		, _day(day)
	{}
	bool operator<(const Date& d) const
	{
		return (_year < d._year) ||
			(_year == d._year && _month < d._month) ||
			(_year == d._year && _month == d._month && _day < d._day);
	}
	bool operator>(const Date& d) const
	{
		return (_year > d._year) ||
			(_year == d._year && _month > d._month) ||
			(_year == d._year && _month == d._month && _day > d._day);
	}
	friend ostream& operator<<(ostream& out, const Date& d)
	{
		out << d._year << "-" << d._month << "-" << d._day;
		return out;
	}
private:
	int _year;
	int _month;
	int _day;
};
void TestPriorityQueue()
{
	// 大堆，需要用户在自定义类型中提供<的重载
	priority_queue<Date> q1;
	q1.push(Date(2023, 12, 1));
	q1.push(Date(2023, 12, 2));
	q1.push(Date(2023, 11, 30));
	cout << q1.top() << endl;
	// 如果要创建小堆，需要用户提供>的重载
	priority_queue<Date, vector<Date>, greater<Date>> q2;
	q2.push(Date(2023, 12, 1));
	q2.push(Date(2023, 12, 2));
	q2.push(Date(2023, 11, 30));
	cout << q2.top() << endl;
}
int main()
{
	TestPriorityQueue();
	return 0;
}

[C++]priority_queue的介绍及模拟实现,c++,开发语言

class Date
{
public:
	Date(int year = 1900, int month = 1, int day = 1)
		: _year(year)
		, _month(month)
		, _day(day)
	{}
	bool operator<(const Date& d) const
	{
		return (_year < d._year) ||
			(_year == d._year && _month < d._month) ||
			(_year == d._year && _month == d._month && _day < d._day);
	}
	bool operator>(const Date& d) const
	{
		return (_year > d._year) ||
			(_year == d._year && _month > d._month) ||
			(_year == d._year && _month == d._month && _day > d._day);
	}
	friend ostream& operator<<(ostream& out, const Date& d)
	{
		out << d._year << "-" << d._month << "-" << d._day;
		return out;
	}
private:
	int _year;
	int _month;
	int _day;
};
void TestPriorityQueue()
{
	//大堆
	priority_queue<Date*> q1;
	q1.push(new Date(2023, 12, 1));
	q1.push(new Date(2023, 12, 2));
	q1.push(new Date(2023, 11, 30));
	cout << q1.top() << endl;

	//小堆
	priority_queue<Date*> q2;
	priority_queue<Date*, vector<int>, greater<Date>> q2;
	q2.push(new Date(2023, 12, 1));
	q2.push(new Date(2023, 12, 2));
	q2.push(new Date(2023, 11, 30));
	cout << q2.top() << endl;
}
int main()
{
	TestPriorityQueue();
	return 0;
}

[C++]priority_queue的介绍及模拟实现,c++,开发语言

class Date
{
public:
	Date(int year = 1900, int month = 1, int day = 1)
		: _year(year)
		, _month(month)
		, _day(day)
	{}
	bool operator<(const Date& d) const
	{
		return (_year < d._year) ||
			(_year == d._year && _month < d._month) ||
			(_year == d._year && _month == d._month && _day < d._day);
	}
	bool operator>(const Date& d) const
	{
		return (_year > d._year) ||
			(_year == d._year && _month > d._month) ||
			(_year == d._year && _month == d._month && _day > d._day);
	}
	friend ostream& operator<<(ostream& out, const Date& d)
	{
		out << d._year << "-" << d._month << "-" << d._day;
		return out;
	}
private:
	int _year;
	int _month;
	int _day;
};
struct PDateLess
{
	bool operator()(const Date* d1, const Date* d2)
	{
		return *d1 < *d2;
	}
};
struct PDateGreater
{
	bool operator()(const Date* d1, const Date* d2)
	{
		return *d1 > *d2;
	}
};
void TestPriorityQueue()
{
	//大堆
	priority_queue<Date*, vector<Date*>, PDateLess> q1;
	q1.push(new Date(2023, 12, 1));
	q1.push(new Date(2023, 12, 2));
	q1.push(new Date(2023, 11, 30));
	cout << *q1.top() << endl;

	//小堆
	priority_queue<Date*, vector<Date*>, PDateGreater> q2;
	q2.push(new Date(2023, 12, 1));
	q2.push(new Date(2023, 12, 2));
	q2.push(new Date(2023, 11, 30));
	cout << *q2.top() << endl;
}
int main()
{
	TestPriorityQueue();
	return 0;
}

[C++]priority_queue的介绍及模拟实现,c++,开发语言

priority_queue的模拟实现

namespace wjq
{
	template <class T>
	struct less
	{
		bool operator()(const T& x, const T& y)
		{
			return x < y;
		}
	};

	template <class T>
	struct greater
	{
		bool operator()(const T& x, const T& y)
		{
			return x > y;
		}
	};
	template <class T, class Container = std::vector<T>, class Compare = less<int>>
	class priority_queue
	{
	private:
		void AdjustUp(size_t child)
		{
			Compare com;//构造一个仿函数对象
			size_t 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 AdjustDown(size_t parent)
		{
			Compare com;//构造一个仿函数对象
			size_t child = 2 * parent + 1;
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
				{
					++child;
				}
				if (com(_con[parent], _con[child]))
				{
					std::swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
	public:
		//无参构造函数
		priority_queue()
		{
			//默认构造函数即可
		}
		//迭代器区间构造
		template <class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
			:_con(first, last)
		{
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; --i)
			{
				AdjustDown(i);
			}
		}
		void push(const T& x)
		{
			_con.push_back(x);
			AdjustUp(_con.size() - 1);//从size-1开始调整
		}
		void pop()
		{
			std::swap(_con[0], _con[_con.size() - 1]);//交换首尾数据
			_con.pop_back();//尾删
			AdjustDown(0);
		}
		const T& top() const
		{
			return _con[0];
		}
		bool empty() const
		{
			return _con.empty();
		}
		size_t size()const
		{
			return _con.size();
		}
	private:
		Container _con;
	};
}

[C++]priority_queue的介绍及模拟实现,c++,开发语言

反向迭代器的底层原理

反向迭代器的本质就是对正向迭代器的封装，它同样是一个适配器。

STL源码中的反向迭代器的实现：反向迭代器用正向迭代器进行构造。

typedef ReverseIterator<iterator, T&, T*> reverse_iterator;
typedef ReverseIterator<const_iterator, const T&, const T*> const_reverse_iterator;
reverse_iterator rbegin() 
{ 
	return reverse_iterator(end());
}
reverse_iterator rend() 
{ 
	return reverse_iterator(begin());
}

[C++]priority_queue的介绍及模拟实现,c++,开发语言

STL源码中，其实正向迭代器和反向迭代器的位置是对称的。通过图示，rbegin()迭代器是最后一个数据的下一个位置，但是通过rbegin()访问的数据应该是6，这是通过运算符重载operator*()来解决。文章来源地址https://www.toymoban.com/news/detail-764913.html

template <class Iterator, class Ref, class Ptr>
Ref operator*()
{
    Iterator tmp = _it;
    return *(--tmp);
}

反向迭代器的模拟实现

namespace wjq
{
	template <class Iterator, class Ref, class Ptr>
	class ReverseIterator
	{
	public:
		RevserseIterator(Iterator it)//使用正向迭代器构造反向迭代器
			:_it(it)
		{}
		Ref operator*()
		{
			Iterator tmp = _it;
			return *(--tmp);
		}
		Ptr operator->()
		{
			return &(operator*());
		}
		typedef ReverseIterator<Iterator, Ref, Ptr> Self
		Self& operator++()
		{
			--_it;
			return *this;
		}
		Self& operator--()
		{
			++_it;
			return *this;
		}
		bool operator!=(const Self& s) const
		{
			return _it != s._it;
		}
	private:
		Iterator _it;//底层是传入类型的迭代器
	};
}

到了这里，关于[C++]priority_queue的介绍及模拟实现的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

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

分享到：
领支付宝红包 赞助服务器费用

相关文章

  • 【C++】priority_queue使用与模拟实现

    【C++】priority_queue使用与模拟实现

    🚀 作者简介：一名在后端领域学习，并渴望能够学有所成的追梦人。 🚁 个人主页：不 良 🔥 系列专栏：🛸C++  🛹Linux 📕 学习格言：博观而约取，厚积而薄发 🌹 欢迎进来的小伙伴，如果小伙伴们在学习的过程中，发现有需要纠正的地方，烦请指正，希望能够与诸君一同

    2024年02月16日
    浏览(41)

  • 优先级队列priority_queue模拟实现

    🌟🌟hello，各位读者大大们你们好呀🌟🌟 🚀🚀系列专栏：【C++的学习】 📝📝本篇内容：C++容器优先级队列priority_queue模拟实现 ⬆⬆⬆⬆上一篇：string模拟实现 💖💖作者简介：轩情吖，请多多指教( •̀֊•́ ) ̖́- ①优先级队列是一种容器适配器，它的第一个元素总是

    2024年02月02日
    浏览(38)
  • C++：模版进阶 | Priority_queue的模拟实现

    C++：模版进阶 | Priority_queue的模拟实现

                                                创作不易，感谢三连支持  模板参数分类为 类型形参与非类型形参 。 类型形参即：出现在模板参数列表中，跟在class或者typename之类的参数类型名称。 非类型形参，就是 用一个常量作为类(函数)模板的一个参数 ，在类(函数

    2024年03月12日
    浏览(42)
  • 【STL】priority_queue的使用及模拟实现

    【STL】priority_queue的使用及模拟实现

    目录 前言 priority_queue的使用 功能解析 基本接口 写点题目 模拟实现 结构解析 插入删除 调整函数结合仿函数 仿函数介绍 结合使用 其他功能 接口补齐 迭代器区间构造 🍾打开 queue 头文件后，我们发现除了我们之前介绍过的普通队列以外，还有一个 priority_queue 。 🍾其又名为

    2024年02月08日
    浏览(39)
  • 【STL详解 —— priority_queue的使用与模拟实现】

    【STL详解 —— priority_queue的使用与模拟实现】

    std::priority_queue 是 C++ 标准库中的容器适配器，它提供了一种基于堆的优先级队列实现。优先级队列是一种特殊的队列，其中的元素按照一定的优先级顺序排列，而不是按照它们被插入的顺序。 在 std::priority_queue 中，插入元素时会根据元素的值自动进行排序，最大（或最小）

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

    【C++初阶】模拟实现优先级队列priority_queue

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

    2024年02月10日
    浏览(37)
  • 【C++】priority_queue模拟实现过程中值得注意的点

    【C++】priority_queue模拟实现过程中值得注意的点

    👀 樊梓慕： 个人主页  🎥 个人专栏： 《C语言》 《数据结构》 《蓝桥杯试题》 《LeetCode刷题笔记》 《实训项目》 《C++》 《Linux》《算法》 🌝 每一个不曾起舞的日子，都是对生命的辜负 本篇文章旨在记录博主在模拟实现priority_queue适配器中遇到的一些问题，希望与大家

    2024年01月23日
    浏览(37)
  • 【C++初阶】仿函数和priority_queue的模拟实现（附源码）

    【C++初阶】仿函数和priority_queue的模拟实现（附源码）

    仿函数，顾名思义就是 模仿函数，它其实是一个类，类里面重载了运算符（） ，在调用这个重载的运算符时，让我们感觉是调用函数一样，可以说相当于C语言里的函数指针一样，但是函数指针的可读性不好，不如仿函数。 1.仿函数即使定义相同，也可能有不同的类型； 2.仿

    2024年02月16日
    浏览(32)
  • C++:stack、queue、priority_queue增删查改模拟实现、deque底层原理

    C++:stack、queue、priority_queue增删查改模拟实现、deque底层原理

    我们先来看看 stack的相关接口有哪些： 从栈的接口，我们可以知道栈的接口是一种特殊的vector，所以我们完全可以使用vector来模拟实现stack。 因此我们可以将底层容器定义成模板，然后将容器类变量作为成员变量进行封装。在实现satck的各种接口时，通过成员变量来调用底层

    2024年02月03日
    浏览(42)
  • 【C++】STL中的容器适配器 stack queue 和 priority_queue 的模拟实现

    【C++】STL中的容器适配器 stack queue 和 priority_queue 的模拟实现

    适配器是一种设计模式 (设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。 例如我们常见的充电器就是一种适配器，它将我们常用的220V交流电压转化为4，5V (或者其他更高的电

    2023年04月26日
    浏览(59)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包