建筑公司做网站的好处,杭州发布最新消息,wordpress资源付费,网站主页如何配色优先级队列
无参构造
priority_queue():c(){}区间构造
区间构造需要用到迭代器#xff0c;而迭代器每个容器的类型不一样#xff0c;所以用模板给出#xff0c;初始化列表#xff0c;把用户给进来的元素空间起始位置#xff0c;放到优先级队列中底层空间的位置#xf…优先级队列
无参构造
priority_queue():c(){}区间构造
区间构造需要用到迭代器而迭代器每个容器的类型不一样所以用模板给出初始化列表把用户给进来的元素空间起始位置放到优先级队列中底层空间的位置然后进行调整把它调整成一个堆
templateclass Iteratorpriority_queue(Iterator first, Iterator last): c(first,last){//将c中的元素调整成堆的结构size_t count c.size();//倒数第一个非叶子结点int root (count - 2) / 2;for (; root 0; root--)AdjustDown(root);}元素操作
void push(const T data){c.push_back(data);//插完元素后破坏了堆的性质重新调整AdjustUp(c.size() - 1);}void pop(){if (empty())return;swap(c.front(), c.back());c.pop_back();//重新调整AdjustDown(0);}size_t size()const{return c.size();}bool empty()const{return c.empty();}//堆顶元素不允许修改因为堆顶元素修改可能会破坏堆的特性const T top() const{return c.front();}向下调整和向上调整
参考下面这个链接里的内容 详解堆的应用
如何判断com中双亲放在前面还是孩子放在前面
默认按照less方式进行比较 less----大堆-------大的元素往上提
com(c[parent],c[child])双亲比孩子小让孩子往上走
bool operator()(const T left ,const T right)
{return left right;
}大于的方式比较-------小堆 小于的方式比较-------大堆
完整代码
#includeiostream
#includealgorithm
#includevector
using namespace std;namespace bite
{templateclass T ,class Container vectorT,class Compare lessTclass priority_queue{public:priority_queue():c(){}templateclass Iteratorpriority_queue(Iterator first, Iterator last): c(first,last){//将c中的元素调整成堆的结构size_t count c.size();//倒数第一个非叶子结点int root (count - 2) / 2;for (; root 0; root--)AdjustDown(root);}void push(const T data){c.push_back(data);AdjustUp(c.size() - 1);}void pop(){if (empty())return;swap(c.front(), c.back());c.pop_back();AdjustDown(0);}size_t size()const{return c.size();}bool empty()const{return c.empty();}//堆顶元素不允许修改因为堆顶元素修改可能会破坏堆的特性const T top() const{return c.front();}private:void AdjustDown(int parent){int child parent * 2 1;while (child c.size()){//找以parent为根的两个孩子中较大的孩子if (child 1 c.size() com(c[child], c[child 1]))child 1;//检测双亲是否满足情况if (com(c[parent] , c[child])){swap(c[child], c[parent]);parent child;child parent * 2 1;}elsereturn;}}void AdjustUp(int child){int parent (child - 1) / 2;while (child){if (com(c[parent] , c[child])){swap(c[child], c[parent]);child parent;parent (child - 1) / 2;}else{return;}}}private:Container c; //存储方式Compare com; //比较方式};}测试
int main()
{int array[] { 8, 1, 9, 3, 6, 4, 5, 0, 2, 7 };bite::priority_queueintq(array, array sizeof(array) / sizeof(array[0]));cout q.top() endl;system(pause);return 0;
}
