今天来简单分享一下写一个极简版的优先级队列。
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这个算是一种难度降低吧，毕竟函数指针有时候会弄错。
