网站正在建设页面,找做柜子的网站,做网站营销公司,网页设计计划书一. 定义 优先级队列是一个容器适配器#xff0c;他可以根据不同的需求采用不同的容器来实现这个数据结构#xff0c;优先级队列采用了堆的数据结构#xff0c;默认使用vector作为容器#xff0c;且采用大堆的结构进行存储数据。 #xff08;1#xff09;在第一个构造函数…一. 定义 优先级队列是一个容器适配器他可以根据不同的需求采用不同的容器来实现这个数据结构优先级队列采用了堆的数据结构默认使用vector作为容器且采用大堆的结构进行存储数据。 1在第一个构造函数中的第三个参数中less是大堆greater是小堆 2第二个构造函数的含义是支持使用容器的迭代器区间进行构造
二. 代码实现与解释
2.1 堆中的向上调整和向下调整
1向上调整插入 在进行插入时我们首先将插入的节点放在最后一个位置上然后进行向上调整。
大堆的向上调整 如果子节点比父节点大则子节点和父节点交换位置
小堆的向上调整 如果子节点比父节点小则子节点和父节点交换位置
2向下调整删除 在进行删除数据时我们会把第需要删除的一个元素和最后一个元素交换位置接着删除尾部的元素然后把第一个元素向下调整到合适的位置。
大堆的向下调整找到父节点后再找到左右节点中较大的那个节点如果父节点小于子节点中较大的那个节点的话则交换位置
小堆的向下调整找到父节点后再找到左右节点中较小的那个节点如果父节点大于子节点中较大的那个节点的话则交换位置
以下是大堆的实现:
templateclass T,class container vectorT
class priority_queue
{
public:void adjust_up(int child){Compare com;size_t parent (child - 1) / 2;while (child 0){if (_con[parent] _con[child]){swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}elsebreak;}}void adjust_down(int parent){int child parent * 2 1;while (child _con.size()){if (child 1 _con.size() _con[child ] _con[child1]){child;}if ( _con[parent] _con[child]){swap(_con[child], _con[parent]);parent child;child parent * 2 1;}elsebreak;}}void pop(){swap(_con[0], _con[size() - 1]);_con.pop_back();adjust_down(0);}const top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}void push(const T x){_con.push_back(x);adjust_up(_con.size()-1);}
private:container _con;
};
2.2 仿函数 定义仿函数就是定义一个类在这个类中我们进行对符号进行运算符重载再用这个类构造一个对象这个对象可以像函数一样去使用以下是仿函数的定义与使用。 意义代替函数指针 Tip有一点我们需要注意 在C库的排序函数中我们想要让函数帮助我们升序或者降序排序时我们也需要传递一个参数给 sort但是在这里我们给sort传递的是一个less或者greater类型的对象而不是像在这里的一个类型。 2.3 任意定义大堆小堆 2.1 中介绍了如何建立一个大堆的结构那么对于不同的场景我们也可能使用小堆那么如果库函数中像2.1这么写的话我们就无法使用小堆了那么为了解决以上的问题我们提出了以下的解决方案。 在函数模板中写一个仿函数的模板
templateclass T,class container vectorT,class Compare LessT 这里的 class container 接收的是一个容器的类型这里默认使用的是vector而 class compare接收的是接受的是一个仿函数的类名默认采用Less。仿函数Less的作用是返回前者是否小于后者的结果Greater 的作用是返回前者是否大于后者的结果。
templateclass T
class Less
{
public:bool operator()(const T x, const T y){return x y;}
};
templateclass T
class Greater
{
public:bool operator()(const T x, const T y){return x y;}
}; 有了这两个仿函数我们就可以把向上调整和向下调整的代码调整为以下写法。
用户想建立一个大堆就可以写
priority_queueint,vectorint,Lessint pq;建立小堆
priority_queueint,vectorint,Greaterint pq; 以下是模拟实现优先级队列的代码
#pragma once
#includevector
namespace hjy
{templateclass Tclass Less{public:bool operator()(const T x, const T y){return x y;}};templateclass Tclass Greater{public:bool operator()(const T x, const T y){return x y;}};templateclass T,class container vectorT,class Compare LessTclass priority_queue{public:void adjust_up(int child){Compare com;size_t parent (child - 1) / 2;while (child 0){if(com(_con[parent],_con[child]))//if (_con[parent] _con[child]){swap(_con[child], _con[parent]);child parent;parent (child - 1) / 2;}elsebreak;}}void adjust_down(int parent){int child parent * 2 1;while (child _con.size()){/*if (child 1 _con.size() _con[child ] _con[child1])*/if (child 1 _con.size()com(_con[child],_con[child1])){child;}if(com(_con[parent]_con[child]))//if ( _con[parent] _con[child]){swap(_con[child], _con[parent]);parent child;child parent * 2 1;}elsebreak;}}void pop(){swap(_con[0], _con[size() - 1]);_con.pop_back();adjust_down(0);}const top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}void push(const T x){_con.push_back(x);adjust_up(_con.size()-1);}private:container _con;};
}
