东莞网站建设seo,网站建设兆金手指排名,wordpress获取作者,seo教程书籍目录 一、priority_queue的介绍
二、 priority_queue的本质
三、priority_queue的使用
四、priority_queue的模拟实现
总结 一、priority_queue的介绍
首先让我们通过阅读优先级队列的官方文档 简单翻译一下 1. 优先队列是一种容器适配器#xff0c;根据严格的弱排序标准…目录 一、priority_queue的介绍
二、 priority_queue的本质
三、priority_queue的使用
四、priority_queue的模拟实现
总结 一、priority_queue的介绍
首先让我们通过阅读优先级队列的官方文档 简单翻译一下 1. 优先队列是一种容器适配器根据严格的弱排序标准它的第一个元素总是它所包含的元素中最大的。 2. 此上下文类似于堆在堆中可以随时插入元素并且只能检索最大堆元素 ( 优先队列中位于顶部的元素) 。 3. 优先队列被实现为容器适配器容器适配器即将特定容器类封装作为其底层容器类 queue 提供一组特定的成员函数来访问其元素。元素从特定容器的“ 尾部 ” 弹出其称为优先队列的顶部。 4. 底层容器可以是任何标准容器类模板也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问并支持以下操作 empty() 检测容器是否为空 size() 返回容器中有效元素个数 front() 返回容器中第一个元素的引用 push_back() 在容器尾部插入元素 5. 标准容器类 vector 和 deque 满足这些需求。默认情况下如果没有为特定的 priority_queue 类实例化指定容器类则使用vector 。 6. 需要支持随机访问迭代器以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、 push_heap 和 pop_heap 来自动完成此操作。 二、 priority_queue的本质 通过阅读优先级队列的模板我们可以看到priority_queue默认使用vector作为底层的存储数据的容器然后在vector之上又使用了堆算法将vector中的元素构成堆的结构因此我们可以认为优先级队列就是堆所有需要的堆的位置都可以使用 priority_queue比如top_k问题。对于堆来说大堆还是小堆是十分关键的让我们将目光看向第三个类模板参数 Compare lesstypename Container::value_type 这里的less是类中仿函数的使用其本质其实就是判断是否小于 此时我们已经彻底了解了优先级队列的本质接下来我们开始学习使用该容器
三、priority_queue的使用 下面我们简单的使用一下上面提到的函数
#include queue
#include iostreamint main() {std::priority_queueint, std::vectorint, std::lessint pq;pq.push(3);pq.push(1);pq.push(4);pq.push(1);while (!pq.empty()) {std::cout pq.top() ;pq.pop();}return 0;
}输出结果为4 3 1 1
在上面的代码中我们创建了一个存储整数的优先队列pq并依次插入了4个元素。然后我们使用top()函数和pop()函数访问和移除元素最后使用empty()函数检查队列是否为空。
其实我们对于优先级队列的使用就是对于堆的使用。
四、priority_queue的模拟实现
最基础的就是建堆
template class InputIterator
priority_queue(InputIterator first, InputIterator last)
{while (first ! last){c.push_back(*first);first;}for (int i (c.size() - 2) / 2; i 0; i)//-1是数组下标里面-1再-1 /2是找 最后一个孩子的爹{AdjustDown(i);}
}//向下调整
void AdjustDown(int parent)
{size_t child parent * 2 1;while (child c.size()){if (child 1 c.size() comp(c[child], c[child 1]))child;//找到最大的左右孩子之一if (comp(c[parent], c[child])){swap(c[parent], c[child]);parent child;child parent * 2 1;}else break;}
}Container c;Compare comp;
其次就是添加和减少 void push(const T x){c.push_back(x);AdjustUp(c.size() - 1);}void AdjustUp(int child){int parent (child - 1) / 2;while (child 0){if(comp(c[parent], c[child])){std::swap(c[parent], c[child]);childparent ;parent (child - 1) / 2;}else break;}}void pop(){std::swap(c[0], c[c.size() - 1]);c.pop_back();AdjustDown(0);}
最后就是其他比较简单的函数 bool empty() const{return c.empty();}size_t size() const{return c.size();}const T top() const{return c[0];}总结
优先队列是一种特殊的队列其中存储的元素按照一定的优先级进行排列。在priority_queue中优先级最高的元素能够快速被访问和删除。
