一、优先级队列
1.1 优先级队列介绍
[优先级队列文档介绍](priority_queue - C++ Reference (cplusplus.com))
- 优先队列是一个容器适配器，根据严格的弱排序标准，它的第一个元素总是它所含的元素中最大的
- 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素(优先队列中位于顶部的元素)
- 优先级队列已经不能称为队列，不符合FIFO特性拉
- 优先队列被实现为容器适配器，容器适配器即将特定的容器类封装作为其底层容器类，queue提供一组特定的成员函数来访问其元素，元素从特定容器的"尾部"弹出，其称为优先队列的顶部
- 底层容器可以是任何标准容器类模板，也可以是特定设计的容器类，容器应该可以通过随机访问迭代器访问，并支持以下操作
- empty():检测容器是否为空
- size():返回容器中有效元素个数
- front():返回容器中第一个元素的引用
- push_back():在容器尾部插入元素
- pop_back():删除容器尾部元素
- 标准容器类vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector
- 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_head,push_heap和pop_heap来自动完成此操作。
1.2 优先级队列使用
优先级队列属于容器适配器，并跟堆具有是否相似的结构与功能，这里可以看成堆。由于堆是通过完全二叉树进行搭建，优先级队列默认使用vector作为其底层存储数据的容器，调用库中priority_queue类使用头文件
默认情况下priority_queue是大堆
#pragma once #include <vector> #include <algorithm> namespace bit { template<class T> class Less { public: bool operator()(const T& x, const T& y) { return x < y; } }; template<class T> class Greater { public: bool operator()(const T& x, const T& y) { return x > y; } }; template<class T, class Containor = vector<T>> class priority_queue { public: void push(const T& x) { _con.push_back(x); adjust_up(_con.size()-1); } void adjust_up(size_t child) { size_t parent = (child - 1) / 2; while (child > 0) { if (_con[parent] < _con[child]) { std::swap(_con[child], _con[parent]); child = parent; parent = (child - 1) / 2; } else break; } } void pop() { std::swap(_con[0], _con[_con.size()-1]); _con.pop_back(); adjust_down(0); } void adjust_down(size_t parent) { size_t child = parent * 2 + 1; while (child < _con.size()) { if (child + 1 < _con.size() && _con[child] < _con[child + 1]) child++; if (_con[parent] < _con[child]) { std::swap(_con[child], _con[parent]); parent = child; child = parent * 2 + 1; } else break; } } const T& top() { return _con[0]; } size_t size() { return _con.size(); } bool empty() { return _con.empty(); } private: Containor _con; }; void test() { priority_queue<int> pq; pq.push(3); pq.push(2); pq.push(2); pq.push(110); while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); } cout << endl; } }
以上就是建堆的逻辑，但是如果需要建小堆，需要去内部修改大于小于号，显得有些繁琐。对此引用了一个类模板适应不同类型，对operator()函数进行运算符重载，作为控制比较逻辑，其中在外部进行开关的控制。
问题:
- 如果需要比较的逻辑，C语言中的sqort函数不行吗？
答:
- C++不喜欢使用qsort函数，参数部分的函数指针显得很麻烦，C++喜欢使用类模板中的仿函数。
1.3 小补充:priority_queue类提供的仿函数
关于仿函数，库中已经实现好了greater和less仿函数可以直接使用，priority_queue默认使用的是less建大堆
二、仿函数
2.1 仿函数概念
仿函数是通过类中运算符重载()实现特定的功能，通过使用匿名对象使用，它的对象可以想函数一样去使用，使得很难区分是调用函数还是调用匿名对象
Less lessfunc; cout << lessfunc(1, 2) << endl; cout << lessfunc.operator()(1, 2) << endl; cout << Less()(1, 2) << endl;
这里推荐使用第二种和第三种，为了提高代码的可读性，第一种写法可能会引起歧义。
2.2 仿函数访问限定符
template<class T> class Less { public: bool operator()(const T& x, const T& y) { return x < y; } }; template<class T> class Greater { public: bool operator()(const T& x, const T& y) { return x > y; } };
仿函数中数据是需要公开使用，对于可以通过strcut或将class访问权限设置为public。仿函数/函数对象可以像函数一样去使用，**但是本质是类调用运算符重载。**那么为什么这么麻烦呢？直接写个函数不就行吗？还仿函数，听起来很牛逼哄哄呀！
【C++】C++ STL探索：Priority Queue与仿函数的深入解析（二）https://developer.aliyun.com/article/1617383
