初识C++ · 优先级队列

  • 开发
  • 7

目录

前言：

1 优先级队列的使用

2 优先级队列的实现

3 仿函数

前言：

栈和队列相对其他容器来说是比较简单的，在stl里面，有一种容器适配器是优先级队列（priority_queue），它也是个队列，但是不大像队列，本文中简略介绍如何使用和模拟实现它。

1 优先级队列的使用

要使用，先文档：

文档黑体第一句话就是，优先级队列是一种容器配置器，容器配置器是？电脑有电源适配器，起到提供电源的作用，但是这个适配器不是充电器，即充电的时候，电源来自于电线，但是我们不能直接拿电线充电吧？这时候适配器就有用了，通过封装，使得两边达到一个配合的效果，容器配置器同理。当然这不是重点。

模板是必要的，模板参数有3个，参考栈和队列，第二个参数是底层用的哪种容器进行实现的，这里的默认是使用的顺序表，第三个参数是仿函数，后面介绍。

那么在来看看成员函数：

很少是吧，可以说成员函数和队列没有什么差别，所以我们现在简单使用一下：

int main()
{
	priority_queue<int> q1;
	q1.push(2);
	q1.push(1);
	q1.push(4);
	q1.push(3);
	q1.push(5);
	cout << q1.size() << endl;

	while (!q1.empty())
	{
		cout << q1.top() << " ";
		q1.pop();
	}
	cout << endl;
	cout << q1.size() << endl;
	return 0;
}

使用很简单，但是打印的结果却，，有点奇怪？

这就是优先级队列的特殊之处了，我们并没有对它进行排序，但是打印出来是默认有序的，这是因为它的本质是堆，而模板参数第三个仿函数的参与，决定了它是大堆还是小堆，默认是升序的，可以理解为升序状态下谁最小谁优先级最高，所以先被打印。

但是实际上，不用管那么多，就把它认为是堆就ok了，所以我们实现的时候需要实现向上调整算法和向下调整算法。

对于仿函数我们放在实现了80%在介绍。

2 优先级队列的实现

我们需要实现以下几个接口：

empty,size,push,pop,top，接口不多，另外还要实现向上调整算法和向下调整算法。

优先级队列的一般结构为：

template <class T,class container = vector<T>>
class priority_queue
{
public:

private:
	container _con;

};

模板的第三个参数先不急。

简单的几个接口我们一股脑实现就完事了：

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

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

void pop()
{
	swap(_con[0], _con[_con.size() - 1]);
	_con.pop_back();
	adjust_down(0);
}

size_t size()
{
	return _con.size();
}

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

这部分是没什么难度的。

随机要实现的是push和pop，这里提问，为什么默认的底层实现是vector呢？

因为堆的本质，就是一块连续的空间，我们只是把它抽象为了完全二叉树。

push数据之后，堆本身的结构被破坏了，所以我们需要向上调整数据，在数据结构初级的时候，已经介绍过两种算法，这里过一下就Ok：

向上调整算法是通过孩子节点和父节点的值进行比较，然后交换位置，可能有点倒反天罡，谁的值大谁就当爸爸？我们知道孩子节点的下标之后，父节点的下标就是（孩子下标 - 1） / 2，如果不熟悉可以拿图推演一下，最后一次交换的时候，孩子节点的下标变成了父节点的下标，所以判断条件应该是孩子节点的下标是否合法，即是否大于0：

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

此时push的的准备工作就做好了，插入，调整，完成：

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

与之对应的是pop，pop对应的准备工作是向下调整算法，向下调整算法有几个需要注意的点就是，我们建大堆，那么就要在孩子节点中找到两个孩子中较大的那一个，除此之后，不是所有的节点都有两个子节点，所以我们需要保证孩子 + 1不小于size，这是基础工作，随机就是比较大小，谁大谁就往上：

void adjust_down(size_t parent)
{
	size_t child = parent * 2 + 1;
	while (child < _con.size())
	{
		if (child + 1 < _con.size() && _con[child] < _con[child + 1])
		{
			child++;
		}
		if (_con[child] > _con[parent])
		{
			swap(_con[child], _con[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}

pop的准备工作也是完毕了，那么pop就行，对于堆部分有些遗忘的同学就会想为什么涉及到向下调整，因为删除，为了效率和不破坏堆的结构，我们的措施是首尾交换，向下调整。

void pop()
{
	swap(_con[0], _con[_con.size() - 1]);
	_con.pop_back();
	adjust_down(0);
}

3 仿函数

仿函数是本文的重点，我们需要先知道什么是仿函数？

先看一段这样的代码：

template <class T>
struct Less
{
	bool operator()(const T& a,const T& b)
	{
		return a > b;
	}
};
void Func(int ,int)
{
	cout << endl;
}

int main()
{
	Less<int> Fun;
	Fun(1,2);
	Func(1,2);
	return 0;
}

如果说只看主函数的代码，就会容易觉得，这不就是两个函数调用吗？仿函数仿函数，顾名思义，模仿函数，因为调用的时候挺像函数的，但是实际上，它是一个类，这个类实例化对象，使用重载后的()，我们称这个过程叫做仿函数调用，仿函数实际上只有一个东西，就是重载的()。

重载的()没有其他东西，只有比较，对于内置类型我们可以直接比较，对于自定义类型我们可能要重载一下> 或者 <。

所以，仿函数是个类，类里面的函数是重载的()，一般是两个参数，用于比较使用。

所以我们在向上调整算法和向下调整算法的实现里面的比较，就可以用仿函数完成，进而控制升序降序，那么我们就还要写两个类：

//仿函数
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 = vector<T>,class compare = greater<T>>


void adjust_up(size_t child)
{
	compare com;
	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
		//if (_con[parent] < _con[child])
		if(com(_con[parent] , _con[child]))
		{
			swap(_con[parent],_con[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

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

向下调整算法这里有个注意的，if(child + 1 < _con.size() && com(_con[child], _con[child + 1]))，第一个判断条件放在前面是最好的，因为越界了不用了比较了，代码逻辑更严密。

但是这里使用了仿函数好像也没有什么特别的，无非就是用了一个像函数调用一样的类而已，为什么不用C语言中qsort里面的函数指针呢？

在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);
	}
private:
	size_t _year;
	size_t _month;
	size_t _day;
};

对于自定义类型的比较重载已经写在了类里面，现在直接比较就可以了：

class DateGreater
{
	bool operator()(const Date& d1, const Date& d2)
	{
		return d1 > d2;
	}
};
class DateLess
{
	bool operator()(const Date& d1, const Date& d2)
	{
		return d1 < d2;
	}
};
void Test2_priority_queue()
{
	priority_queue<Date> q1;
	q1.push({ 2024, 4, 17 });
	q1.push({ 2024, 4, 18 });
	q1.push({ 2024, 4, 19 });
	q1.push({ 2024, 4, 20 });
	cout << q1.size() << endl;
	while (!q1.empty())
	{
		cout << q1.top() << " ";
		q1.pop();
	}
	cout << endl;
}

对比淘宝，淘宝的的排序，比如综合评分排序，销量排序等，用户点击对应按钮，系统就会调用对应的函数，使用的就是仿函数，函数指针在C++里面不太常用，它的类型和变量名混杂一起，看起来不太舒服。

仿函数的一般使用差不多了，但是如果我们给优先级队列里面存放日期类的指针，但是相比较日期类的大小怎么办呢？

void Test3_priority_queue()
{
	priority_queue<Date*, vector<Date*>> q1;
	q1.push(new Date(2024,5,20));
	q1.push(new Date(2024,5,21));
	q1.push(new Date(2024,5,22));
	q1.push(new Date(2024,5,23));
	while (!q1.empty())
	{
		cout << *(q1.top()) << " ";
		q1.pop();
	}
	cout << endl;
}

比如这样，里面都是指针，我们push的也是new出来的指针，我们使用的仿函数是：

class DateGreater
{
	bool operator()(const Date& d1, const Date& d2)
	{
		return d1 > d2;
	}
};
class DateLess
{
	bool operator()(const Date& d1, const Date& d2)
	{
		return d1 < d2;
	}
};

那么这个仿函数就不可以了，比较出来的都是随机结果，这是因为new出来的地址都是随机的，而默认的是比较的指针，打印出来的是对应的日期，所以结果一会儿是对的一会儿是错的，这是因为仿函数的错误使用，我们应该解引用之后再进行比较，这里就要另外提供一个仿函数了：

class PDateGreater
{
public:
	bool operator()(Date* d1, Date* d2)
	{
		return *d1 > *d2;
	}	
};

光提供了还不行，我们还要显式调用：

void Test3_priority_queue()
{
	priority_queue<Date*, vector<Date*>,PDateGreater> q1;
	q1.push(new Date(2024,5,20));
	q1.push(new Date(2024,5,21));
	q1.push(new Date(2024,5,22));
	q1.push(new Date(2024,5,23));
	while (!q1.empty())
	{
		cout << *(q1.top()) << " ";
		q1.pop();
	}
	cout << endl;
}

这样就是完美的了。仿函数的简单介绍就到这里。

感谢阅读！

阅读全部

相关推荐

  10. 初识C#语言

    2024-06-06 08:50:03       36 阅读

最近更新

  4. TCP协议是安全的吗?

    2024-06-06 08:50:03       18 阅读

  12. 阿里云服务器执行yum，一直下载docker-ce-stable失败

    2024-06-06 08:50:03       19 阅读

  13. 【Python教程】压缩PDF文件大小

    2024-06-06 08:50:03       18 阅读

  18. 通过文章id递归查询所有评论（xml）

    2024-06-06 08:50:03       20 阅读

热门阅读

  3. 【k8s的三种探针】

    2024-06-06 08:50:03       8 阅读

  5. Scala学习笔记7: 对象

    2024-06-06 08:50:03       7 阅读

  9. 小程序真题合集

    2024-06-06 08:50:03       7 阅读

  12. HW面试应急响应之场景题

    2024-06-06 08:50:03       8 阅读

  16. IDEA 开发中一些好用的插件

    2024-06-06 08:50:03       8 阅读

  18. 微信小程序中实现录音功能及其功效

    2024-06-06 08:50:03       6 阅读

  24. 【AI】DeepStream(09)：deepstream-app源码详解

    2024-06-06 08:50:03       8 阅读

  25. 从零开始精通Onvif之设备发现

    2024-06-06 08:50:03       13 阅读

  26. 扩展 Kafka 集群从三台节点到四台节点的过程

    2024-06-06 08:50:03       8 阅读

  28. web应用中的robots.txt配置

    2024-06-06 08:50:03       8 阅读

  29. Python爬虫之BeautifulSoup模块

    2024-06-06 08:50:03       9 阅读