【CPP】优先级队列

今天来简单分享一下写一个极简版的优先级队列。

1.什么是优先级队列？？？

优先级队列属于STL中队列的一种，虽然包含在队列容器里，但它并不是真正的队列。
在本质上，优先级队列更像一个堆，默认是大堆。
链接：LINK

下面我们简单来认识一下优先级队列的基本使用。

2.优先级队列的基本使用与理解

优先级队列的主要接口有下面这些：

// 优先级队列，默认底层是大堆。
priority_queue<int> ps;
ps.push(2);
ps.push(3);
ps.push(4);
ps.push(1);while (!ps.empty())
{cout << ps.top() << " ";ps.pop();
}

那可以让他变成小堆吗？当然可以。但是需要用到仿函数。

// 优先级队列，可以用仿函数置为小堆
priority_queue<int, vector<int>, greater<int>> pq;
pq.push(2);
pq.push(3);
pq.push(4);
pq.push(1);while (!pq.empty())
{cout << pq.top() << " ";pq.pop();
}

这里区分两个概念：取出结果是有序与真正排序的区别。
在上面优先级队列中，我们发现while+top取出的数据是有序的，这是因为我们每次取得都是堆顶元素。至于怎么弄的，可以参考C数据结构钟堆删除数据时候得操作，首尾交换，然后size–，我觉得应该是相同的操作。

// 我们发现sort默认排序为升序。
vector<int> v = { 1,3,4,2 };
vector<int>::iterator it = v.begin();
while (it != v.end())
{cout << *it << " ";it++;
}
cout << endl;sort(v.begin(), v.end());
it = v.begin();
while (it != v.end())
{cout << *it << " ";it++;
}

为了让sort变成升序，我们也可以用仿函数进行设置。

vector<int> v = { 1,3,4,2 };
vector<int>::iterator it = v.begin();
while (it != v.end())
{cout << *it << " ";it++;
}
cout << endl;sort(v.begin(), v.end(), greater<int>());
it = v.begin();
while (it != v.end())
{cout << *it << " ";it++;
}

重点区分一个地方：模板参数与函数参数的需要
priority_queue<int, vector<int>, greater<int>> pq;
sort(v.begin(), v.end(), greater<int>());
我们发现两个greater一个带括号一个不带，这是什么情况呢？

要注意优先级队列是一种模板，需要的是类型进行实例化，而sort是模板实例化出来的一种函数，需要迭代器区间和具体的比较仿函数对象，而不是仅仅一个仿函数类型就行。

3.优先级队列的模拟实现

#pragma once
#include<vector>
#include<iostream>
using namespace std;template<typename T>
struct Less
{
public:bool operator()(const T& x, const T& y){return x < y;}
};template<typename T>
struct Greater
{
public:bool operator()(const T& x, const T& y){return x > y;}
};template<class T, class Container = vector<T>, class Compare = Greater<T>>
class periority_queue
{
private:Container _con;
public:void adjust_up(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[child], _con[parent])){swap(_con[child], _con[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}}void push(const T& x){_con.push_back(x);adjust_up(_con.size() - 1);}void adjust_down(int parent){Compare com;int child = parent * 2 + 1;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child + 1], _con[child])){child = child + 1;}if (com(_con[child], _con[parent])){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();adjust_down(0);}size_t size(){return _con.size();}bool empty(){return _con.empty();}const T& top(){return _con[0];}
};

其实大部分接口实现都是复用vector的，但是插入和删除接口的逻辑还需要重点看一下。整体没什么难点，需要注意的是我们实现用了一个comper的东西去控制是建小堆/大堆。
comper传的是仿函数类型。我们在向上/向下调整算法中使用这个仿函数类型生成了仿函数(函数对象)进行控制。

引入仿函数的意义：
在本实例中，仿函数是用来控制是建大堆/小堆的，我们C语言可以传函数指针来控制，这个CPP的话比较习惯用仿函数，说白了就是传入一个特殊类对象来控制，感觉无论是C语言的传函数指针还是CPP传仿函数如果控制得当都挺好用，当然前提是C语言那个指针得玩的明白。CPP这个算是一种难度降低吧，毕竟函数指针有时候会弄错。

---

EOF