🌈个人主页：秋风起，再归来~

🔥系列专栏：C++从入门到起飞          

🔖克心守己，律己则安

目录

1、priority_queue的介绍

2、priority_queue的使用

3、priority_queue的模拟实现 

3.1、仿函数的介绍

3.2、模拟实现源码

4、完结散花

1、priority_queue的介绍

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素 中最大的。

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

3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue 提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的 顶部。

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

>empty()：检测容器是否为空

>size()：返回容器中有效元素个数

>front()：返回容器中第一个元素的引用

>push_back()：在容器尾部插入元素

>pop_back()：删除容器尾部元素

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

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

2、priority_queue的使用

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

3、priority_queue的模拟实现 

3.1、仿函数的介绍

在之前的文章中我提到过关于sort第三个参数的问题，当时我称他为比较器，事实上它更仿函数有关！

 仿函数其实就是一个类里面进行了操作符（）的重载，我们用这个类实例化一个对象再调用它重载的（）就可以比较两个元素的大小！

下面举一个简单的示例代码：

<code>template<class T>

class compareLess

{

public:

bool operator()(const T& a1,const T& a2)

{

return a1 < a2;

}

};

int main()

{

compareLess<int> less;

int a = 30;

int b = 20;

cout<<less.operator()(a,b)<<endl;

return 0;

}

<code>//cout<<less.operator()(a,b)<<endl;

cout<<less(a,b)<<endl;

重载函数的调用可以简化为 less(a,b)，我们会发现它的调用形式和函数非常相像，不同的是less是我们实例化出来的对象的名字，并不是函数名，因此，我们称其为仿函数！

现阶段我们看到仿函数看起来非常简单，确实如此，不过，我们在后面会遇到和仿函数有关的更为复杂的内容！

好啦，我们再来看到优先级队列，我们会发现它的模版参数里面也有仿函数的身影，原因也很简单，我们知道优先级队列就是堆，那我们在实现堆的时候必然会用到向上和向下调整的算法。而这些算法也一定会有元素的大小比较，如果我们在类里面实现的是一个大堆，那我们下次要用到小堆的时候怎么办呢！难道临时打电话给程序员叫他修改一下比较符号吗？显然不可能，难道实现俩个类吗，这两个类的代码高度相似，只有一些比较大小的符号不同，这样做并不合理。

这时候我们就可以通过传递比较器的方法来解决这个问题了！ 

<code>//向上调整

void AdjustUp()

{

//用比较器实例化一个对象

compare comp;

int child = con.size() - 1;

int parent = (child - 1) / 2;

while (child > 0)

{

//仿函数取大向上调整

if (comp(con[parent], con[child]))

{

swap(con[child], con[parent]);

child = parent;

parent = (child - 1) / 2;

}

else

{

break;

}

}

}

在优先级队列实例化出对象之前，我们不知道你具体的比较逻辑！只有使用者在传递模版参数之后才可以确定！

3.2、模拟实现源码

这篇文章的主要目的是让我们初步了解仿函数并熟悉priority_queue，至于priority_queue的模拟实现其实非常简单（如果我们之前对数据结构中的堆学的还不错的话，这两个向上和向下调整算法也是手到擒来的！）下面我就直接给源码给大家参考一下了！

#pragma once

#include<iostream>

#include<algorithm>

#include<list>

#include<vector>

#include<deque>

using namespace std;

namespace my_priority_queue

{

//仿函数（比较器）

template<class T, class container = vector<T>, class compare = less<T>>

class priority_queue

{

public:

//元素数量

size_t size()

{

return con.size();

}

//判空

bool empty()

{

return con.size() == 0;

}

//向上调整

void AdjustUp()

{

//用比较器实例化一个对象

compare comp;

int child = con.size() - 1;

int parent = (child - 1) / 2;

while (child > 0)

{

//仿函数取大向上调整

if (comp(con[parent], con[child]))

{

swap(con[child], con[parent]);

child = parent;

parent = (child - 1) / 2;

}

else

{

break;

}

}

}

//入栈

void push(const T& val)

{

con.push_back(val);

//向上调整

AdjustUp();

}

//向下调整

void AdjustDown()

{

compare comp;

int parent = 0;

int child = parent * 2 + 1;//左孩子

while (child < con.size())

{

//如果右孩子更大就更新孩子

if ((child < con.size() - 1 )&& comp(con[child ], con[child+1]))

{

child++;

}

//仿函数向下调整

if (comp(con[parent], con[child]))

{

swap(con[child], con[parent]);

parent = child;

child = parent * 2 + 1;

}

else

{

break;

}

}

}

//出栈

void pop()

{

swap(con[0], con[con.size() - 1]);

con.pop_back();

AdjustDown();

}

//取优先级高元素

const T& top()

{

return con[0];

}

private:

container con;

};

}

4、完结散花

好了，这期的分享到这里就结束了~

如果这篇博客对你有帮助的话，可以用你们的小手指点一个免费的赞并收藏起来哟~

如果期待博主下期内容的话，可以点点关注，避免找不到我了呢~

我们下期不见不散~~