文章目录
- priority_queue简介
- priority_queue的实现
- Myless和Mygreater
- push
- pop
- 常规接口
- 全部代码
- 测试代码
- 总结
priority_queue简介
priority_queue是优先级队列。
什么是优先级队列？
优先级队列（Priority Queue）是一种数据结构，用于管理一组元素，使得每个元素都有一个关联的优先级，并且元素按照优先级进行排序和访问。优先级队列常用于调度算法、图算法（如Dijkstra算法）、操作系统任务管理等场景。它的主要特点是可以快速地插入元素和找到具有最高优先级的元素。
简单来说优先级队列就是一个堆，在STL底层默认是大堆，堆顶的元素是堆里最大的，搞懂了优先级队列，其实大概得几个接口我们也知道了，就是插入和删除还有几个常规的判空之类的。
为了更好的实现优先级队列，我们先来做做铺垫，我们看官方文档给出的模版参数
前两个我们都很熟悉了，第一个就是普通的模版参数，第二个是容器适配器，第三个是我们接下来要介绍的，仿函数。
什么事仿函数？
int main()
{
Myless<int> l;
l(1, 2);
return 0;
}
看上面代码，如果单看上面的代码的话，如果不看类的实例化，这很容易让人误会这是在调用一个名字是l的函数，但是如果我们把上面这个类给写出来呢？
template<class T>
class Myless
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
private:
};
其实这是一个重载了operator()的函数，这个函数的操作是由我们确定的，所以我们可以像调用函数一样，去调用类的成员函数。
仿函数概念：仿函数（Functor）也被称为函数对象（Function Object），是指一个可以像函数一样使用的对象。它是通过重载类的函数调用运算符operator()来实现的。仿函数在许多场景中都非常有用，例如在标准模板库（STL）中用于算法和容器。
我们通过控制仿函数的行为可以控制类中的比较的操作，也就是说，我们可以控制这个类到底是建小堆还是建大堆。
priority_queue的实现
Myless和Mygreater
由于我们要控制建大堆和建小堆，所以我们创建两个类，类的成员函数只有一个就是operator()用于控制优先级队列中的比较操作，当我们要建大堆的时候就调用Myless，这里在模版参数里，我们默认给的就是建大堆的Myless，如果大家还是不能理解的话接下来看了下面的代码，应该更能理解。
我们先将两个类定义出来：
template<class T>
class Myless
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
class Mygreater
{
public:
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
模版参数：
template<class T, class Container = vector<int>, class Compare = Myless<T>>
push
由于优先级队列就类似于堆，所以和堆的操作类似，我们先将元素尾插，然后进行向上调整算法进行建堆操作
void push(const T& x)
{
_con.push_back(x);
Adjust_Up(_con.size() - 1);
}
void Adjust_Up(int child)
{
Compare confunc;
int parent = (child - 1) / 2;
while (child > 0)
{
if (confunc(_con[parent], _con[child]))
{
std::swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
pop
由于pop最后一个数据是没什么意义的，所以这里我们pop的是堆顶的数据，直接pop堆顶的数据，我们需要重新建堆付出的代价太大了，所以这里我们将收尾两个元素交换，然后直接pop队尾的数据，这样只有堆顶的数据是不符合堆的定义的，所以我们只需要向下调整即可。
const T& top()
{
return _con.front();
}
void Adjust_Down(int parent)
{
Compare confunc;
int child = parent * 2 + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && confunc(_con[child], _con[child + 1]))
{
child++;
}
//默认建大堆
if (confunc(_con[parent], _con[child]))
{
std::swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
可以看到在向上调整算法和向下调整算法中我们都用到了我们的仿函数，先创建一个对象，然后调用这个类的operator()，这个函数的行为就是去控制大于和小于，从而达到控制建小堆还是建大堆，如果是缺省参数，就直接建大堆，如果是调用Mygreater就建小堆。
常规接口
size_t size()
{
return _con.size();
}
const T& top()
{
return _con.front();
}
bool empty()
{
return _con.empty();
}
全部代码
namespace lyrics
{
template<class T>
class Myless
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
class Mygreater
{
public:
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
template<class T, class Container = vector<int>, class Compare = Myless<T>>
class priority_queue
{
public:
priority_queue() = default;
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
while (first != last)
{
_con.push_back(*first);
first++;
}
//从最下面的第一个非叶子节点开始调整
for (int i = (_con.size() - 1 - 1) / 2;i >= 0;i--)
{
Adjust_Down(i);
}
}
void push(const T& x)
{
_con.push_back(x);
Adjust_Up(_con.size() - 1);
}
void pop()
{
std::swap(_con[0], _con[_con.size() - 1]);
_con.pop_back();
Adjust_Down(0);
}
void Adjust_Down(int parent)
{
Compare confunc;
int child = parent * 2 + 1;
while (child < _con.size())
{
if (child + 1 < _con.size() && confunc(_con[child], _con[child + 1]))
{
child++;
}
//默认建大堆
if (confunc(_con[parent], _con[child]))
{
std::swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
void Adjust_Up(int child)
{
Compare confunc;
int parent = (child - 1) / 2;
while (child > 0)
{
if (confunc(_con[parent], _con[child]))
{
std::swap(_con[parent], _con[child]);
child = parent;
parent = (child - 1) / 2;
}
else
{
break;
}
}
}
size_t size()
{
return _con.size();
}
const T& top()
{
return _con.front();
}
bool empty()
{
return _con.empty();
}
private:
Container _con;
};
}
测试代码
void test()
{
vector<int> v{ 1,2,3,4,5,6,7 };
lyrics::priority_queue<int> pq(v.begin(), v.end());
while (!pq.empty())
{
cout << pq.top() << ' ';
pq.pop();
}
lyrics::priority_queue<int> pq1(v.begin(), v.end());
pq1.push(8);
cout << endl;
cout << endl << pq1.size() << endl;
while (!pq1.empty())
{
cout << pq1.top() << ' ';
pq1.pop();
}
cout << endl << pq1.size() << endl;
}
总结
在本篇博客中，我们深入探讨了优先级队列（priority_queue）的实现及其在各种应用中的重要性。通过详细的代码示例，我们演示了如何利用堆数据结构高效地管理具有优先级的元素，展示了优先级队列在插入、查找和删除操作中的性能优势。无论是在调度算法、图算法还是操作系统任务管理中，优先级队列都展现出了不可或缺的作用。
此外，我们还介绍了仿函数（Functor）这一强大的编程概念。通过重载函数调用运算符，仿函数可以像普通函数一样使用，但同时具备存储状态、实现灵活逻辑和代码复用的优点。通过具体的C++和Python代码示例，我们展示了如何定义和使用仿函数，并讨论了其在标准模板库（STL）和实际编程中的应用场景。
总的来说，理解和掌握优先级队列和仿函数这两个概念，对于提升编程能力和编写高效、灵活的代码具有重要意义。希望通过本篇博客的讲解，读者能够更好地理解这两个重要的编程技术，并在实际项目中加以应用。如果你对优先级队列或仿函数有任何疑问或建议，欢迎在评论区留言，我们共同探讨、学习进步。
