STL-priority_queue的使用及其模拟实现

      优先级队列(priority_queue)默认使用vector作为其底层存储数据的容器，在vector上又使用了堆算法将vector中的元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。

注意： 默认情况下priority_queue是大堆。

priority_queue的使用

priority_queue的构造函数

模板参数 Compare

在 std::priority_queue 类中，通过模板参数 Compare 来指定用于比较元素的函数对象，从而影响堆的排序方式。Compare 是一个仿函数，它定义了元素之间的比较方式。根据不同的 Compare，优先队列可以变成大堆（最大堆）或小堆（最小堆）。

默认的 std::less<T>（大堆）：
std::less 是一个函数对象，它重载了 operator()，用于比较两个元素。它返回一个布尔值，表示是否第一个参数小于第二个参数。在默认情况下，如果不提供 Compare 参数，优先队列使用 std::less 作为比较函数对象，即大堆。这意味着在大堆中，父节点的值总是大于或等于子节点的值。

std::greater<T>（小堆）：
std::greater<T> 是另一个函数对象，它重载了 operator()，用于比较两个元素。与 std::less<T> 不同，std::greater<T> 返回一个布尔值，表示第一个参数是否大于第二个参数。如果你将 std::greater<T> 传递给 priority_queue，它将会构造一个小堆。在小堆中，父节点的值总是小于或等于子节点的值。

仿函数

仿函数（Functor）是一种重载了函数调用操作符 operator() 的类对象，使得该对象可以像函数一样被调用。它实际上是一种函数对象，它可以具有自己的成员变量和操作，同时可以在使用上类似于普通函数。

使用仿函数的主要优点之一是可以将函数的行为和状态封装在对象中，从而使代码更具有可读性和可维护性。仿函数可以用于各种情况，包括标准算法、STL容器和其他需要函数式操作的地方。

例如：

// 仿函数/函数对象
template<class 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->大堆
template<class 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 Less<Date*>
{
    bool operator()(const Date* x, const Date* y)
    {
        return *x < *y;
    }
};

// Compare进行比较的仿函数 greater->小堆

template<class T>
class Greater
{
public:
    bool operator()(const T& x, const T& y)
    {
        return x > y;
    }
};
template<class T, class Container = vector<T>, class Compare = Less<T>>
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_queue<int> 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_queue<Date,vector<Date>,Less<Date>> q1;
    q1.push(Date(2018, 10, 29));
    q1.push(Date(2018, 10, 28));
    q1.push(Date(2018, 10, 30));
    cout << q1.top() << endl;
    priority_queue<Date*, vector<Date*>> q3;
    //priority_queue<Date*, vector<Date*>,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_queue<Date, vector<Date>, Greater<Date>> 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::vector<T>），和 Compare（用于比较元素的仿函数，默认为 std::less<T>）

Compare 是一个模板参数，用于进行元素的比较。它是一个仿函数，可以是 std::less<T>（默认）或 std::greater<T>，具体取决于用户提供的优先队列类型。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]，获取优先队列的顶部元素。