《数据结构》随笔——priority

定义于头文件< queue >

template<
    class T,
    class Container = std::vector,
    class Compare = std::less
> class priority_queue;

模板形参：

• T -存储的元素类型
• Container -用于存储元素的底层容器类型。容器必须满足序列容器 (SequenceContainer) 的要求，另外，它必须提供拥有通常语义的下列函数：
  • front()
  • push_back()
  • pop_back()
• Compare -提供严格弱序的比较 (Compare) 类型。（priority_queue默认是最大堆，也就是将最大元素输出，其比较函数里，一般是第一参数在弱序中先于其第二参数则返回 true ，如果改为最小堆，则需要对比较函数进行修改。）

greater和less是头文件< functional>

template  struct greater {
  bool operator() (const T& x, const T& y) const {return x>y;}
  typedef T first_argument_type;
  typedef T second_argument_type;
  typedef bool result_type;
};

template  struct less {
  bool operator() (const T& x, const T& y) const {return x 
在STL库中，已有常见的类型重载，因此在涉及到STL类型元素建立堆时，可以直接使用该函数。比如创建一个int类型的最大堆和最小堆
 
#include 
#include 
#include 
priority_queue, greater> min_q; // 最小堆
priority_queue, less> max_q;  // 最大堆
 
 
 
该怎么区分？
 无论是greater还是less函数，其传入的两个参数：第一参数X，第二参数Y，均是当函数为true的时候，把第一参数放在堆底，第二参数往后放。因此，当使用greater()的时候，跳出两个数中较大的数，将其放在堆底，这样堆顶就是最小元素，就实现了最小堆。同理，最大堆亦是如此。
 
 
如果不是STL类型呢？
 这里举例结点类
 
struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};
 
此时需要手动实现结构体的比较运算符< , > 的重载。此处给出了两种实现比较运算符的重载方法，第一种是友元函数；第二种是重载运算符，不添加的话会报错，因为编译器编译器限定，运算符“<”内部只需读取对象成员变量，体现出大小比较的原则即可，禁止对成员变量进行修改。所以，重载运算符“<”的实现必须要求const限定。
 
struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
    friend bool operator >(const struct ListNode& x, const struct ListNode& y);
    bool operator < (const ListNode& y) const { // 注意，此处必须添加const，否则会报错
        return this->val < y.val;
    }
};

inline bool operator >(const struct ListNode& x, const struct ListNode& y) {
    return x.val > y.val;
}

    priority_queue, greater> min_q; // 最小堆
    priority_queue, less> max_q;  // 最大堆
 
 
如果不允许修改结构体呢？ 这里就用到了第二种方法，自行编写compare函数
 
3. 利用自定义compare函数来实现最小堆、最大堆 
struct ListNode {
    int val;
    ListNode* next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode* next) : val(x), next(next) {}
};

struct cmp {
    bool operator()(ListNode a, ListNode b) {
        return a->val > b->val;
    }
};

    priority_queue, cmp> q; // 最小堆