提供网站建设服务,招聘网站排行榜,郑州做网站hnqfu,开发公司交房前财务交付风险优先级队列(priority_queue)默认使用vector作为其底层存储数据的容器#xff0c;在vector上又使用了堆算法将vector中的元素构造成堆的结构#xff0c;因此priority_queue就是堆#xff0c;所有需要用到堆的位置#xff0c;都可以考虑使用priority_queue。
注意#xff1… 优先级队列(priority_queue)默认使用vector作为其底层存储数据的容器在vector上又使用了堆算法将vector中的元素构造成堆的结构因此priority_queue就是堆所有需要用到堆的位置都可以考虑使用priority_queue。
注意 默认情况下priority_queue是大堆。
priority_queue的使用 priority_queue的构造函数 模板参数 Compare
在 std::priority_queue 类中通过模板参数 Compare 来指定用于比较元素的函数对象从而影响堆的排序方式。Compare 是一个仿函数它定义了元素之间的比较方式。根据不同的 Compare优先队列可以变成大堆最大堆或小堆最小堆。
默认的 std::lessT大堆 std::less 是一个函数对象它重载了 operator()用于比较两个元素。它返回一个布尔值表示是否第一个参数小于第二个参数。在默认情况下如果不提供 Compare 参数优先队列使用 std::less 作为比较函数对象即大堆。这意味着在大堆中父节点的值总是大于或等于子节点的值。
std::greaterT小堆 std::greaterT 是另一个函数对象它重载了 operator()用于比较两个元素。与 std::lessT 不同std::greaterT 返回一个布尔值表示第一个参数是否大于第二个参数。如果你将 std::greaterT 传递给 priority_queue它将会构造一个小堆。在小堆中父节点的值总是小于或等于子节点的值。
仿函数
仿函数Functor是一种重载了函数调用操作符 operator() 的类对象使得该对象可以像函数一样被调用。它实际上是一种函数对象它可以具有自己的成员变量和操作同时可以在使用上类似于普通函数。
使用仿函数的主要优点之一是可以将函数的行为和状态封装在对象中从而使代码更具有可读性和可维护性。仿函数可以用于各种情况包括标准算法、STL容器和其他需要函数式操作的地方。
例如
// 仿函数/函数对象 templateclass T class Less { public: bool operator()(const T x, const T y) { return x y; } }; empty()检查优先队列是否为空size()用于获取优先队列中元素的数量top()获取优先队列的顶部元素最大或最小元素取决于堆的类型但不改变队列的内容push()用于将新元素添加到优先队列中emplace()在优先队列中插入一个新元素
pop():将优先队列的顶部元素移除同时会重新调整堆以维持堆的性质
swap(): 用于交换调用对象和传递的参数 x 之间的内容,将两个优先队列的内容互换但不会改变它们的比较函数或其他属性 模拟实现priority_queue
// Compare进行比较的仿函数 less-大堆 templateclass T class Less { public: bool operator()(const T x, const T y) { return x y; } }; class Date { public: Date(int year 1900, int month 1, int day 1) : _year(year) , _month(month) , _day(day) {} bool operator(const Date d)const { return (_year d._year) || (_year d._year _month d._month) || (_year d._year _month d._month _day d._day); } bool operator(const Date d)const { return (_year d._year) || (_year d._year _month d._month) || (_year d._year _month d._month _day d._day); } friend ostream operator(ostream _cout, const Date d) { _cout d._year - d._month - d._day; return _cout; } private: int _year; int _month; int _day; };
//类模板特化 template struct LessDate* { bool operator()(const Date* x, const Date* y) { return *x *y; } };
// Compare进行比较的仿函数 greater-小堆
templateclass T class Greater { public: bool operator()(const T x, const T y) { return x y; } }; templateclass T, class Container vectorT, class Compare LessT class priority_queue { public: priority_queue() {} template class InputIterator priority_queue(InputIterator first, InputIterator last) :_con(first, last) { // ½¨¶Ñ for (int i (_con.size() - 2) / 2; i 0; --i) { adjust_down(i); } } void adjust_up(int child) { Compare com; int parent (child - 1) / 2; while (child 0) { //有名对象 if (com(_con[parent], _con[child])) //匿名对象 //if (Compare()(_con[parent], _con[child])) //if (_con[parent] _con[child]) { swap(_con[child], _con[parent]); child parent; parent (child - 1) / 2; } else { break; } } } void adjust_down(int parent) { Compare com; size_t child parent * 2 1; while (child _con.size()) { //if (child 1 _con.size() // // _con[child] _con[child 1]) if (child 1 _con.size() com(_con[child], _con[child 1])) { child; } //if (_con[parent] _con[child]) if (com(_con[parent], _con[child])) { swap(_con[child], _con[parent]); parent child; child parent * 2 1; } else { break; } } } void push(const T x) { _con.push_back(x); adjust_up(_con.size() - 1); } void pop() { swap(_con[0], _con[_con.size() - 1]); _con.pop_back(); adjust_down(0); } const T top() { return _con[0]; } bool empty() { return _con.empty(); } size_t size() { return _con.size(); } private: Container _con; };
class PDateLess { public: bool operator()(const Date* p1, const Date* p2) { return *p1 *p2; } }; class PDateGreater{ public: bool operator()(const Date* p1, const Date* p2) { return *p1 *p2; } }; void test_priority_queue() { priority_queueint pq; pq.push(1); pq.push(2); pq.push(3); pq.push(4); pq.push(1); while (!pq.empty()) { cout pq.top() ; pq.pop(); } cout endl; } void test_priority_queue2() { // 大堆需要用户在自定义类型中提供的重载 priority_queueDate,vectorDate,LessDate q1; q1.push(Date(2018, 10, 29)); q1.push(Date(2018, 10, 28)); q1.push(Date(2018, 10, 30)); cout q1.top() endl; priority_queueDate*, vectorDate* q3; //priority_queueDate*, vectorDate*,PDateLess q3; q3.push(new Date(2018, 10, 29)); q3.push(new Date(2018, 10, 28)); q3.push(new Date(2018, 10, 30)); cout *(q3.top()) endl; // 如果要创建小堆需要用户提供的重载 priority_queueDate, vectorDate, GreaterDate q2; q2.push(Date(2018, 10, 29)); q2.push(Date(2018, 10, 28)); q2.push(Date(2018, 10, 30)); cout q2.top() endl; }
成员函数的模拟实现
模板类 priority_queue 这是一个模板类它代表了一个优先队列的实现。它接受三个模板参数T元素类型Container底层容器类型默认为 std::vectorT和 Compare用于比较元素的仿函数默认为 std::lessT
Compare 是一个模板参数用于进行元素的比较。它是一个仿函数可以是 std::lessT默认或 std::greaterT具体取决于用户提供的优先队列类型。Compare 仿函数用于确定在堆中的元素排序方式从而决定了是最大堆还是最小堆。在 priority_queue 类的各个成员函数中通过调用 Compare 仿函数来进行元素的比较从而实现了插入和调整堆的操作。
构造函数 priority_queue() 这是一个默认构造函数不需要使用 Compare 仿函数进行比较。
构造函数模板 priority_queue(InputIterator first, InputIterator last) 在构造函数内部使用 Compare 仿函数来执行比较操作以确定元素的顺序。在添加元素后通过调用 adjust_down 函数来构建堆。
成员函数 adjust_up(size_t child) 在上浮操作中使用 Compare 仿函数执行比较以确定是否需要交换父子节点的位置从而保持堆的性质。
成员函数 push(const T x) 在插入操作中首先将新元素添加到底层容器 _con然后通过调用 adjust_up 函数来执行上浮操作保证新元素位于合适的位置。
成员函数 adjust_down(size_t parent) 在下沉操作中使用 Compare 仿函数执行比较以确定是否需要交换父子节点的位置从而保持堆的性质。
成员函数 pop() 在删除操作中首先将顶部元素与底层容器的最后一个元素交换然后通过调用 adjust_down 函数来执行下沉操作保证堆的性质。
成员函数 const T top() 通过返回 _con[0]获取优先队列的顶部元素。
