网站建设方案书制作流程,广州学校论坛网站建设,网站规划与建设规划书,网站有哪些平台一、priority_queue是什么 priority_queue 是容器适配器#xff0c;它提供常数时间的#xff08;默认#xff09;最大元素查找#xff0c;对数代价的插入与释出。
可用用户 提供的 Compare 更改顺序#xff0c;例如#xff0c;用 std::greaterT 将导致最小元素作…一、priority_queue是什么 priority_queue 是容器适配器它提供常数时间的默认最大元素查找对数代价的插入与释出。
可用用户 提供的 Compare 更改顺序例如用 std::greaterT 将导致最小元素作为 top() 出现。
用 priority_queue 工作类似管理某些随机访问容器中的堆优势是不可能突然把堆非法化。 二、使用
priority_queue实际就是把优先级最高的一个数据放在最前面大/小堆。
#includequeue
#includeiostream
using namespace std;void test_pq()
{vectorint v { 0,8,7,1,9 };priority_queueint q(v.begin(), v.end());q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);while (!q.empty()){cout q.top() endl;q.pop();}}int main()
{test_pq();return 0;
} 三、模拟实现
#includeiostream
#includevector
#includefunctionalnamespace gu
{template class T, class Container vectorT, class Compare lessT class priority_queue{public:priority_queue(){}template class InputIteratorpriority_queue(InputIterator first, InputIterator last):c(first,last){for (int i (c.size() - 2) / 2; i 0; i--){adjust_down(i);}}bool empty() const{return c.empty();}size_t size() const{return c.size();}const T top(){return c[0];}void adjust_down(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 child * 2 1;}else{break;}}}void adjust_up(int child){int parent (child - 1) / 2;while (child 0){if (comp(c[parent], c[child])){swap(c[child], c[parent]);child parent;parent (child - 1) / 2;}else{break;}}}void push(const T x){c.push_back(x);adjust_up(c.size() - 1);}void pop(){swap(c[0], c[c.size() - 1]);c.pop_back();adjust_down(0);}private:Container c;Compare comp;};};
