行业网站做的好的,网站建设公司天强科技,wordpress 网站建设,响应式网站的研究意义priority_queue的相关介绍
优先级队列是一种容器适配器#xff0c;根据严格的排序标准#xff0c;它的第一个元素总是它所包含的元素中最大(小)的。该容器适配器类似于堆#xff0c;在堆中可以随时插入元素#xff0c;并且可以检索最大(小)堆元素(优先级队列中位于顶部的元…priority_queue的相关介绍
优先级队列是一种容器适配器根据严格的排序标准它的第一个元素总是它所包含的元素中最大(小)的。该容器适配器类似于堆在堆中可以随时插入元素并且可以检索最大(小)堆元素(优先级队列中位于顶部的元素)。优先级队列被实现为容器适配器容器适配器即 将特定容器类封装作为其底层容器类queue提供一组特定的成员函数来访问其元素。元素从特定容器的“尾部”弹出其称为优先级队列的顶部。底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应可以通过随机访问迭代器访问。标准容器类vector和deque皆满足这些需求。默认情况下如果没有为特定的priority_queue类实例化指定容器类则使用vector。
更多关于priority_queue的详细内容请点击priority_queue的文档介绍
priority_queue的使用 优先级队列默认使用vector作为其底层存储数据的容器在vector上又使用了堆算法将vector中元素构造成堆的结构因此priority_queue就是堆所有需要用到堆的位置都可以考虑使用priority_queue。注意默认情况下priority_queue是大堆。 函数声明接口说明 priority_queue() priority_queue(InputIterator first, InputIterator last) 无参构造 迭代器区间初始化构造 empty()检查优先级队列是否为空top()返回优先级队列中最大(最小元素)即堆顶元素push(x)在优先级队列中插入元素xpop()删除优先级队列中最大(最小)元素即堆顶元素
// 使用举例(和queue类似)
int arr[] { 3,2,7,6,0,4,1,9,8,5 };
// 迭代器区间初始化
priority_queueint pq1(arr, arr sizeof(arr) / sizeof(arr[0]));while (!pq1.empty()) // 判断优先级队列是否为空
{cout pq1.top() ; // 获取栈顶元素pq1.pop(); // 删除元素
}
cout endl;
// 结果为9,8,7,6,5,4,3,2,1,0
上述代码结果默认是大堆(降序)其默认仿函数为less()若想得到升序序列只需改变仿函数为greater()即可。
// 改变仿函数
priority_queueint, vectorint, greaterint pq1(arr, arr sizeof(arr) / sizeof(int));
priority_queue的底层实现
ps. 默认情况下创建的是大堆其底层按照小于号比较
// 迭代器区间初始化
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); //向下调整算法}
}
// 向上调整算法
void AdjustUp(int child)
{int parent (child - 1) / 2;while (child 0){// 使用仿函数if (_comFunc(_con[parent], _con[child])){swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}elsebreak;}
}
// 插入
void push(const T x)
{_con.push_back(x);AdjustUp(_con.size() - 1);
}
// 向下调整算法
void AdjustDown(int parent)
{size_t child parent * 2 1;while (child _con.size()){// 使用仿函数if (child 1 _con.size() _comFunc(_con[child], _con[child 1])){child;}if (_comFunc(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent child;child parent * 2 1;}elsebreak;}
}
//删除
void pop()
{swap(_con[0], _con[_con.size() - 1]);_con.pop_back();AdjustDown(0);
}
