C++：模拟实现priority_queue

HZzzzzLu

发布于 2024-11-26 08:22:35

18600

代码可运行

文章被收录于专栏：codingcoding

运行总次数：0

代码可运行

priority_queue的介绍

概念

在C++标准库中，priority_queue是一个基于优先级堆的容器适配器。它的底层容器是vector，将其封装成堆来管理元素，确保元素按照特定的优先级顺序排列。

默认情况下，priority_queue是大堆，因为其的比较函数是std::less，如果想要建立小堆，则使用std::greater比较函数，这个比较函数其实是仿函数，接下来会提及。

特点

1.自动排序

元素根据优先级自动排序，最高优先级的元素总是在队列的前端。

2.只访问前端元素

只能访问队列的前端元素，即最高优先级的元素。

3.底层容器

使用vector作为底层容器来存储元素，但用户不能直接访问这个容器。

4.元素比较

priority_queue需要一个比较函数或函数对象来确定元素的优先级顺序，默认情况下使用std:less，即最大值优先。

priority_queue的使用

基本操作

empty()：检查队列是否为空。
size()：返回队列中的元素数量。
top()：访问队列前端的元素（不删除）。
pop()：移除队列前端的元素。
push()：向队列添加新元素。

演示代码

int main()
{
	std::priority_queue<int, vector<int>, less<int>> pq;
	pq.push(2);
	pq.push(1);
	pq.push(4);
	pq.push(5);
	pq.push(3);

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

	return 0;
}

priority_queue的模拟实现

仿函数

要想实现priority_queue，我们首先需要了解仿函数。

在 C++ 中，仿函数（Functor）是一种重载了函数调用操作符 operator() 的类或结构体。仿函数可以像函数一样被调用，但它们实际上是对象，因此可以拥有成员变和成员函数。

仿函数是函数对象（function object）的一种，它们通常用于需要函数指针或函数引用的地方，尤其是当需要传递具有特定行为的对象时。

仿函数的一些关键特性：

重载 operator()：仿函数必须重载函数调用操作符 operator()，使其能够像函数一样被调用。
状态存储：仿函数可以拥有自己的数据成员，这些成员存储了仿函数的状态。
行为封装：仿函数可以封装特定的行为，这些行为可以通过其 operator() 实现。
灵活性：仿函数提供了比普通函数更多的灵活性，因为它们可以存储状态，并且可以被重载。
STL 兼容性：仿函数与 STL 容器和算法兼容，可以作为算法的参数传递。

仿函数的简单示例

上面我们提到std::less就是一个仿函数，我们就来模拟实现下。

template<class T>
class Less
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};

向上调整和向下调整

我们知道priority_queue其实是堆，既然是堆那就需要实现向上调整和向下调整算法。

void AdjustDown(int parent)
{
	int 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]))
		{
			swap(_con[parent], _con[child]);
			parent = child;
			child = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}

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

模拟实现的代码

template<class T>
class Less
{
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 AdjustDown(int parent)
	{
		int 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]))
			{
				swap(_con[parent], _con[child]);
				parent = child;
				child = 2 * parent + 1;
			}
			else
			{
				break;
			}
		}
	}

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

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

	//删除堆顶的元素
	void pop()
	{
		swap(_con[0], _con[_con.size() - 1]);
		_con.pop_back();
		AdjustDown(0);
	}

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

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

	int size() const
	{
		return _con.size();
	}


private:
	Container _con;
	Compare _com;
};

拜拜，下期再见😏

摸鱼ing😴✨🎞