priority_queue优先级队列的模拟实现
本章目标
1.优先级队列的模拟实现
1.优先级队列的模拟实现
对于优先级队列,priority_queue它的本质是一个堆,底层是用vector实现的一个堆.
有关于优先级队列的使用与堆并无二已但是它有第三个参数.是一个仿函数,默认生成的的是一个大堆,但是传了一个less的仿函数.
private:container _con;compare cmp;
它有两个成员变量,优先级队列也是使用适配器模式实现的,只要底层支持下标的随机访问即可.
1.1向上调整算算法以及向下调整算法
堆的本质上是一个完全二叉树,它的向上调整算法是从子结点去找父节点,从下向上调整
void adjustup(size_t child)
{size_t parents = (child - 1) / 2;while (child > 0){//if (_con[child] > _con[parents])if(cmp(_con[parents],_con[child])){std::swap(_con[child], _con[parents]);child = parents;parents = (child - 1) / 2;}else{break;}}}
我们用c++实现的时候,不用可以去关注大堆小堆的逻辑,这个由仿函数控制,以及它的底层的swap函数我们也可以不需要自己写,直接用标准库中的即可.
void adjustdown(size_t parents)
{size_t child = parents * 2 + 1;while (child < _con.size()){//if (child + 1 < _con.size() && _con[child + 1] > _con[child])if (child + 1 < _con.size() &&cmp( _con[child ] , _con[child+1])){child++;}//if (_con[child] > _con[parents])if(cmp(_con[parents],_con[child])){std::swap(_con[child], _con[parents]);parents = child;child = parents * 2 + 1;}else {break;}}
向下调整算法是已知父节点去调整子结点,但它由要求调整的树的左右子树一定是一个堆.,我们在实现中的逻辑是用的左节点的逻辑.我们要判断左右结点哪一个是较小或者较大.还要保证右结点也是在堆的size范围内.
1.2插入删除
1对于堆的插入,我们只需要调用尾插,然后用向上调整算法调整堆的结构.
void push(const T& val)
{_con.push_back(val);adjustup(_con.size() - 1);
}
删除
对于删除来说,我们依旧遵循交换删除调整的逻辑,首位元素交换,删除尾部元素,最后进行向下调整,因为只有首位元素交换,这样左右子树仍然是一个堆.
void pop()
{std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjustdown(0);
}
对于堆顶元素我们仅提供一个版本,只读不能修改,因为堆顶元素进行修改,会导致堆的结构会被破坏
const T& top()const
{return _con[0];
}
迭代器区间构造
复用push
template <class InputIterator>priority_queue(InputIterator first, InputIterator last)
{while (first != last){push(*first++);}
}
我们用模板的偏特化,保证传过来指针的时候也能实现.
template <class T>
struct greater
{bool operator()(const T& a, const T& b){return a > b;}
};
template<class T>
struct less
{bool operator()(const T& a, const T& b){return a < b;}
};
template<class T>
struct less<T*>
{bool operator()(const T* const& p1, const T* const& p2){return *p1 < *p2;}
};
参考代码
template <class T>
struct greater
{bool operator()(const T& a, const T& b){return a > b;}
};
template<class T>
struct less
{bool operator()(const T& a, const T& b){return a < b;}
};
template<class T>
struct less<T*>
{bool operator()(const T* const& p1, const T* const& p2){return *p1 < *p2;}
};
template <class T, class container = vector<T>,class compare = less<T>>
class priority_queue
{
public:priority_queue(){}template <class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first != last){push(*first++);}}void push(const T& val){_con.push_back(val);adjustup(_con.size() - 1);}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjustdown(0);}const T& top()const{return _con[0];}bool empty()const{return _con.empty();}size_t size()const{return _con.size();}
private:container _con;compare cmp;void adjustup(size_t child){size_t parents = (child - 1) / 2;while (child > 0){//if (_con[child] > _con[parents])if(cmp(_con[parents],_con[child])){std::swap(_con[child], _con[parents]);child = parents;parents = (child - 1) / 2;}else{break;}}}void adjustdown(size_t parents){size_t child = parents * 2 + 1;while (child < _con.size()){//if (child + 1 < _con.size() && _con[child + 1] > _con[child])if (child + 1 < _con.size() &&cmp( _con[child ] , _con[child+1])){child++;}//if (_con[child] > _con[parents])if(cmp(_con[parents],_con[child])){std::swap(_con[child], _con[parents]);parents = child;child = parents * 2 + 1;}else {break;}}}
};