目录
一、priority_queue的介绍和使用
1.1 priority_queue的介绍
1.2 priority_queue的基本接口
二、仿函数的介绍
2.1 基本概念
2.2 适用场景
三、模拟实现priority_queue
3.1 向上调整算法
3.2 向下调整算法
3.3 整体框架
一、priority_queue的介绍和使用
1.1 priority_queue的介绍
- 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。
- 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)。
- 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出，其称为优先队列的顶部。
- 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：
empty()：检测容器是否为空
size()：返回容器中有效元素个数
front()：返回容器中第一个元素的引用
push_back()：在容器尾部插入元素pop_back()：删除容器尾部元素
5. 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类 实例化指定容器类，则使用vector。
6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用 算法函数make_heap、push_heap和pop_heap来自动完成此操作。
1.2 priority_queue的基本接口
| 函数声明 | 接口说明 |
| priority_queue()/priority_queue(first, last) | 构造一个空的优先级队列 |
| empty( ) | 检测优先级队列是否为空，是返回true，否则返 false |
| top( ) | 返回优先级队列中最大(最小元素)，即堆顶元素 |
| push(x) | 在优先级队列中插入元素x |
| pop() | 删除优先级队列中最大(最小)元素，即堆顶元素 |
如有不清晰的，可以去查看http://cplusplus.com具体的文档
二、仿函数的介绍
2.1 基本概念
仿函数是一种可被调用的对象，它可以像函数一样被使用。在C++中，仿函数是一种重载了函数调用运算符 operator() 的类或结构体，它可以被当作函数来调用，接受参数并返回结果。
在刚刚我们所讲的priority_queue就可以看到仿函数的使用：
看这个 less 这个模板参数，它其实就是一个仿函数接口，这里我们简单的介绍一下less
less这个仿函数实现的功能其实就是让我们的优先队列变成大堆，与之相对应的就是greater这个仿函数，其被引入进优先队列的作用是让其变成小堆。
大概懂了仿函数是个什么样的东西，那我们大概的来模拟实现less一下吧。
class less
{
bool opeartor()(int x,int y)
{
return x<y;
}
}写仿函数需要注意，他一定是用class进行修饰的，且其主要是对（）进行的重载，我们写的这个less只适用于整型未免太单调了，我们不妨给他加个模板。
template<class T>
class less
{
bool opeartor()(T x,T y)
{
return x<y;
}
}2.2 适用场景
- 首先就是priority_queue这个容器需要仿函数这个接口，当我们使用自定义类型时，需要我们自己编写一个仿函数接口。
- 再比如说使用 sort 时，其同样有一个仿函数的接口，举例：
实现一个升序排序：
vector<int> st={1,9,8,5,6,7,3,2,1,4};
sort(st.begin(),st.end(),greater<int>);
三、模拟实现priority_queue
要知道priority_queue实际上是一个堆，既然是堆，那就会涉及到我们的向上调整算法和向下调整算法，这也是我们的主要编写内容。
3.1 向上调整算法
void adjust_up(int child)
{
int parent = (child - 1) / 2;
while (parent >= 0)
{
if (comp(c[parent], c[child]))
{
std::swap(c[parent], c[child]);
}
else
break;
child = parent;
parent = (child - 1) / 2;
}
} 这里可以发现我们的比较方法是使用的仿函数，这样就可以根据我们传入的仿函数的不同来定义不同的堆，是不是很方便。
这里如果不是很懂的话可以去查看一下堆的知识。
3.2 向下调整算法
void adjust_down(int parent)
{
int child = parent * 2 + 1;
while (child < size())
{
if (child+1<size()&&comp(c[child], c[child+1]))
{
child += 1;
}
if (comp(c[parent], c[child]))
{
std::swap(c[child], c[parent]);
}
else
break;
parent = child;
child = parent * 2 + 1;
}
}可不要忘了向下调整算法的边界判断哦。
3.3 整体框架
接口实现方面，和之前的内容差不多，这里我直接给大家上代码
namespace bit
{
template <class T, class Container = vector<T>, class Compare = less<T> >
class priority_queue
{
public:
void adjust_up(int child)
{
int parent = (child - 1) / 2;
while (parent >= 0)
{
if (comp(c[parent], c[child]))
{
std::swap(c[parent], c[child]);
}
else
break;
child = parent;
parent = (child - 1) / 2;
}
}
void adjust_down(int parent)
{
int child = parent * 2 + 1;
while (child < size())
{
if (child+1<size()&&comp(c[child], c[child+1]))
{
child += 1;
}
if (comp(c[parent], c[child]))
{
std::swap(c[child], c[parent]);
}
else
break;
parent = child;
child = parent * 2 + 1;
}
}
priority_queue()
{}
template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
:c(first,last)
{
for (int i = (size() - 1 - 1) / 2; i >= 0; i--)
{
adjust_down(i);
}
}
bool empty() const
{
return c.empty();
}
size_t size() const
{
return c.size();
}
const T& top() const
{
return c[0];
}
void push(const T& x)
{
c.push_back(x);
adjust_up(size() - 1);
}
void pop()
{
std::swap(c[0], c[size() - 1]);
c.pop_back();
adjust_down(0);
}
private:
Container c;
Compare comp;
};
};
