【priority_queue的使用及模拟实现】—— 我与C++的不解之缘（十六）
前言
priority_queue，翻译过来就是优先级队列，但是它其实是我们的堆结构（如果堆一些遗忘的可以看一下前面的文章复习一下【数据结构】二叉树——顺序结构——堆及其实现_二叉树顺序结构-CSDN博客），本篇文章就来使用并且模拟实现一下priority_queue。
priority_queue的使用
这个容器接口就这些，使用起来比较简单：这里就简单使用一下。
int main()
{
priority_queue<int> pq1;//无参构造
int arr[] = { 1,5,8,9,2,10,6 };
//使用一段迭代器区间构造(这里可以使用数组,因为原始指针可以像迭代器那样使用)
priority_queue<int> pq2(arr, arr + sizeof(arr) / sizeof(arr[0]));
//依次输出pq2
while (!pq2.empty())
{
cout << pq2.top() << " ";
pq2.pop();
}
cout << endl;
//往pq1插入数据
pq1.push(1);
pq1.push(5);
pq1.push(7);
pq1.push(8);
pq1.push(9);
//依次输出pq1
while (!pq1.empty())
{
cout << pq1.top() << " ";
pq1.pop();
}
cout << endl;
return 0;
}
输出结果如下：
10 9 8 6 5 2 1
9 8 7 5 1
经过观察，我们会发现，默认构建的都是大堆，先看一下容器priority_queue 的定义
这里有三个模版参数，第一个是数据类型，第二个是容器类型（默认是vector)，第三个是compare 默认是 less（这个是一个仿函数，再模拟实现后面再讲解）。
我们不难发现，只有第三个模版参数才也可能控制是大堆还是小堆，（这里，我们如果要建小堆传**greater**即可）。
//建小堆
int main()
{
priority_queue<int, vector<int>, greater<int>> pq1;
pq1.push(9);
pq1.push(7);
pq1.push(5);
pq1.push(3);
pq1.push(2);
while (!pq1.empty())
{
cout << pq1.top() << " ";
pq1.pop();
}
cout << endl;
return 0;
}
2 3 5 7 9
这样就建了小堆；对于仿函数，在模拟实现之后，我相信就会有了深刻的理解。
priority_queue模拟实现
通过看priority_queue的定义，我们不难发现其也是一个容器适配器，默认容器是vector；所以它的成员变量就是一个容器，其的每一个操作就是在容器中进行一系列操作。
先来看一下priotity_queue的大致内容：
namespace HL
{
//默认——大堆
template<class T, class Contianer = vector<T>, class Compare = less<T>>
class priority_queue
{
//向下调整算法
void AdjustDown(int parent)
{}
//向上调整算法
void AjustUp(int child)
{}
public:
//默认构造
priority_queue() {}
//迭代器区间构造
template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{}
void push(const T& x) {}
void pop() {}
T& top() {}
const T& top()const {}
size_t size()const {}
bool empty()const {}
private:
Contianer _con;
};
}
1、向上调整算法
所谓向上调整算法，就是向上调整当前节点，使其满足堆结构。
主要应用：插入节点时，最后一个节点（插入的节点）向上调整。
//向上调整算法
void AjustUp(int child)
{
int parent = (child - 1) / 2;
while (parent >= 0)
{
if (_con[parent] < _con[child])
{
std::swap(_con[parent], _con[child]);
}
else
{
break;
}
child = parent;
parent = (child - 1) / 2;
}
}
2、向下调整算法
所谓向上调整算法，就是向下调整当前节点，使其满足堆结构。
主要应用：
- 构造堆结构时，从最后一个节点的父节点开始依次向下调整，创建堆结构。
- 删除节点时，第一个（堆顶）与最后一个（堆底）交换，然后让第一个（堆顶）节点向下调整。
void AdjustDown(int parent)
{
int child = 2 * parent + 1;
while (child < _con.size())
{
if (child < _con.size() - 1 && _con[child] < _con[child + 1])
{
child++;
}
if (_con[parent] < _con[child])
{
std::swap(_con[parent], _con[child]);
}
else
{
break;
}
parent = child;
child = 2 * parent + 1;
}
}
3、构造函数
构造函数有两种，一是默认构造函数，另一个就是使用迭代器区间构造。
1.默认构造
//默认构造
priority_queue() {}
2.迭代器区间构造
迭代器区间，这里就先将数据插入到容器（vector）中，再从最后一个节点的父节点开始，依次往下调整建堆即可。
//迭代器区间构造
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--)
{
AdjustDown(i);
}
}
4、push、pop、top
push: 插入数据，然后向上调整，保持堆结构。
void push(const T& x)
{
_con.push_back(x);
AdjustUp(_con.size() - 1);
}
pop: 删除数据（删除堆顶数据），堆顶数据与堆低数据交换，然后从堆顶位置向下调整即可。
void pop()
{
std::swap(_con[0], _con[_con.size() - 1]);
AdjustDown(0);
}
top: 返回堆顶数据
T& top()
{
return _con[0];
}
const T& top()const
{
return _con[0];
}
5、size、empty、swap
size: 返回堆中的数据个数
size_t size()const
{
return _con.size();
}
empty: 判断堆是否为空
bool empty()const
{
return _con.empty();
}
swap: 交换函数
void swap(priority_queue& pq)
{
std::swap(_con, pq._con);
}
到这里，priority_queue 大致就实现成功了一半，因为这里我们只实现了大堆。
接下来，我们来看一下仿函数，如何实现大小堆。
仿函数
仿函数，也是STL中比较中要的内容；
那为什么叫做仿函数呢？因为，他实际上是一个类，这个类重载了operator() 这样，我们就可以像函数应用实使用这个类。
先来看一下仿函数**less**：
//这里可以使用struct（默认成员是共有）
template<class T>
class Less
{
public:
bool operator()(const T& x, const T& y)
{
return x < y;
}
};
template<class T>
class Greater
{
public:
bool operator()(const T& x, const T& y)
{
return x > y;
}
};
这里实现了仿函数**Less** 和**Greater**，我们可以像函数那样去使用这个类。
int main()
{
HL::Less<int> l;
cout << (l(11, 22)) << endl;
return 0;
}
greater 与less类似，greater 是判断大的（就是，返回的是 x>y)。
知道了仿函数，再回头看一下**priority_queue** 第三个模板参数，这个模板参数就是来控制大小堆的（默认是less，就是大堆；如果我们传greater 就是小堆。）
这样我们再修改一下，向上调整算法和向下调整算法，让我们可以通过这个模板参数来控制大小堆。
//向下调整算法
void AdjustDown(int parent)
{
Compare com;
int child = 2 * parent + 1;
while (child < _con.size())
{
//if (child < _con.size() - 1 && _con[child] < _con[child + 1])
if (child < _con.size() - 1 && com(_con[child], _con[child + 1]))
{
child++;
}
//if (_con[parent] < _con[child])
if (com(_con[parent] , _con[child]))
{
std::swap(_con[parent], _con[child]);
}
else
{
break;
}
parent = child;
child = 2 * parent + 1;
}
}
//向上调整算法
void AdjustUp(int child)
{
Compare com;
int parent = (child - 1) / 2;
while (parent >= 0)
{
//if (_con[parent] < _con[child])
if (com(_con[parent] , _con[child]))
{
std::swap(_con[parent], _con[child]);
}
else
{
break;
}
child = parent;
parent = (child - 1) / 2;
}
}
这里测试一下，使用模拟实现的堆进行排序，pq1建大堆，排降序；pq2建小堆，排升序。
void test_priority_queue()
{
HL::priority_queue<int,vecotr<int>, HL::Less<int>> pq1;
pq1.push(1);
pq1.push(7);
pq1.push(3);
pq1.push(5);
pq1.push(9);
while (!pq1.empty())
{
cout << pq1.top() << " ";
pq1.pop();
}
cout << endl;
int arr[] = { 1,3,5,7,9,8,6,4,2 };
HL::priority_queue<int,vector<int>,HL::Greater<int>> pq2(arr, arr + sizeof(arr) / sizeof(arr[0]));
while (!pq2.empty())
{
cout << pq2.top() << " ";
pq2.pop();
}
cout << endl;
}
int main()
{
test_priority_queue();
return 0;
}
9 7 5 3 1
1 2 3 4 5 6 7 8 9
到这里，priority_queue 使用以及模拟实现就完成了，感谢各位的支持。
继续加油！！！
我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws
Greater<int>> pq2(arr, arr + sizeof(arr) / sizeof(arr[0]));
while (!pq2.empty())
{
cout << pq2.top() << " ";
pq2.pop();
}
cout << endl;
}
int main()
{
test_priority_queue();
return 0;
}
9 7 5 3 1
1 2 3 4 5 6 7 8 9
到这里，priority_queue 使用以及模拟实现就完成了，感谢各位的支持。
继续加油！！！
我的博客即将同步至腾讯云开发者社区，邀请大家一同入驻：https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws