C++--priority_queue和仿函数

目录

 1.priority_queue

实现：

2.仿函数

priority_queue+仿函数 实现代码

1.priority_queue

       优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的，其实就是个堆，默认是大根堆。

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

简单实现：

#pragma once
#include<iostream>
#include<vector>
using namespace std;
namespace ch
{
    template <class T, class Container = vector<T>>
    class priority_queue
    {
    public:
 
        priority_queue(){}
 
        void adjust_up(int child) //向上调整算法
        {
            size_t parent = (child - 1) / 2;
            while (child > 0)
            {
                if (c[parent] < c[child])
                {
                    swap(c[parent], c[child]);
                    child = parent;
                    parent = (child - 1) / 2;
                }
                else
                {
                    break;
                }
            }
        }
 
        void adjust_down(int parent) //向下调整算法
        {
            size_t child = parent * 2 + 1;
            while (child < c.size())
            {
                if (child + 1 < c.size() && c[child] < c[child + 1])
                {
                    child++;
                }
                if (c[parent] < c[child])
                {
                    swap(c[parent], c[child]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else
                {
                    break;
                }
            }
        }
 
        template <class InputIterator>
        priority_queue(InputIterator first, InputIterator last)
        {
            while (first != last)
            {
                c.push(*first);
                first++;
            }
 
            for (int i = (c.size() - 1 - 1) / 2; i >= 0; i--) //建堆，时间复杂度为O(N)
            {
                adjust_down(i);
            }
        }
 
        bool empty() const
        {
            return c.empty();
        }
 
        size_t size() const
        {
            return c.size();
        }
 
        const T& top()
        {
            return c[0];
        }
 
        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;
    };
 
};

引入仿函数实现定义类型时就能决定大小堆 

2.仿函数

    就是定义一个类，类中只有一个重载了()的成员函数，可以有传入参数，需要调用时创建其对象，如：

class Print{

  void operator()(){
       cout<<"hehe"<<endl;
  }

};
int main(){

   Print p;
   p();

}

所以我们写个大于小于逻辑的仿函数，并在创建priority_queue时传入此类即可

priority_queue+仿函数 实现代码

    //小于仿函数
    template<class T>
    class myless {
    public:
        bool operator()(const T& x,const T& y) {
            return x < y;
        }
    };

    //大于仿函数
    template<class T>
    class mygreater {
    public:
        bool operator()(const T& x, const T& y) {
            return x > y;
        }
    };

    template <class T, class Container = vector<T>, class Compare = myless<T> >
    class priority_queue
    {
    public:

        priority_queue() = default;

        template <class InputIterator>
        priority_queue(InputIterator first, InputIterator last) {
            while (first != last) {
                c.push_back(*first);
                first++;
            }
            for (int i = (size()-1-1) / 2; i >= 0; i--) {
                adjust_down(i);
            }
        }

        bool empty() const {
            return c.empty();
        }

        size_t size() const {
            return c.size();
        }

        const T& top() const {
            assert(!empty());
            return c[0];
        }

        void adjust_up(size_t child) {
            while (child > 0) {
                size_t parent = (child - 1) / 2;
                if (comp(c[parent] , c[child])) {
                    swap(c[parent], c[child]);
                }else {
                    break;
                }
                child = parent;
            }
        }

        void push(const T& x) {
            c.push_back(x);
            adjust_up(c.size()-1);
        }

        void adjust_down(size_t parent) {
            size_t child = parent * 2 + 1;
            while (child < size()) {
                if (child + 1 < size() && comp(c[child] , c[child + 1])) {
                    child++;
                }
                if (comp(c[parent] , c[child])) {
                    swap(c[child], c[parent]);
                    parent = child;
                    child = child * 2 + 1;
                }
                else {
                    break;
                }

            }
        }

        void pop() {
            assert(!empty());
            swap(c[0], c[size() - 1]);
            c.erase(c.end()-1);
            adjust_down(0);
        }

    private:

        Container c;
        Compare comp;
    };