c++手册

定义

定义:priority_queue<Type, Container, Functional>在这里插入图片描述

分析

priority_queue <int,vector<int>,less<int> >q;
默认使用容器vector,使用less< T >进行比较,默认为大顶堆。
Q:默认less比较,重载了operator<,应该是升序,为什么是大顶堆?
A:这个问题需要从源码角度分析:
堆push时调用的代码:

__push_heap(_RandomAccessIterator __first, _Distance __holeIndex,
            _Distance __topIndex, _Tp __value, _Compare __comp)
    //__holeIndex  新添加节点的索引,即叫做孔洞
    //__topIndex  顶端索引
    //__value   新添加节点的值
    //__comp    比较函数,传入为less
{
  _Distance __parent = (__holeIndex - 1) / 2;   //找到新节点父节点索引
  while (__holeIndex > __topIndex && __comp(*(__first + __parent), __value)) {
      //若孔洞没有到达最顶端  &&  父节点的值小于新添加节点的值,则要进行下列操作
      //less中,左边比右边小则返回true,与less愿意相同
    *(__first + __holeIndex) = *(__first + __parent);   //将父节点的值放入孔洞
    __holeIndex = __parent; //孔洞的索引编程了原来父节点的索引,往上移动了
    __parent = (__holeIndex - 1) / 2;   //那么孔洞的父节点又要继续往上找
  }
  *(__first + __holeIndex) = __value; //将新添加节点的值放在找到的位置(孔洞)
}

传入的comp就是为了在比较新加入的值value与父节点值的大小,若返回true,才会进行交换操作。
如果传入less< int>,则在父节点比value的小时,comp为true,value上升,父节点下移,对应了大根堆的上溯。greater< int>同理。

在这里插入图片描述

//std::less::operator() 
constexpr bool operator()(const T &lhs, const T &rhs) const 
{
    return lhs < rhs;
}

我们可以按自己需求,修改compare类
【TIP】compare 形参如果是引用,必须使用常量引用
在这里插入图片描述

cmp写法

函数对象

struct CmpByValueLess {//如果类定义了调用运算符,则该类的对象称作函数对象
    bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
        return lhs.second < rhs.second;//大顶堆,若>则为小顶堆
    }
};
vector<int> topKFrequent(vector<int>& nums, int k) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, CmpByValueLess> queue;
    //...
}

函数指针

使用普通函数指针或静态成员函数指针。

class Solution {
public:  
		//静态成员函数才相当于外部普通函数
        static bool cmp(pair<int, int>& a, pair<int, int>& b)
        { 
            return b.second<a.second; 
        }
        vector<int> topKFrequent(vector<int>& nums, int k) {
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)*> freq(cmp);
		//...
    }
};

lambda函数

lambda函数可以直接引用捕获,使用函数内其他变量。

vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {
    using PII=pair<int,int>;
    auto cmp=[&](const PII& a ,const PII& b){
        return A[a.first]*1.0/A[a.second]>A[b.first]*1.0/A[b.second];
    };
    priority_queue<PII,vector<PII>,decltype(cmp)> smallHeap(cmp);
    //...
}

重载operator< 或 >

重载大于小于号
大根堆使用less,重载operator<;
小根堆使用greater,重载operator>。

struct point {
    int val, x, y;
    point(int val, int x, int y) : val(val), x(x), y(y) {}
    bool operator> (const point& a) const { 
    //后面的const表示函数为常量函数,可以对常量对象使用,如果没有const,则常量point无法重载>
        return val > a.val; 
    }
    //另一种写法
    // friend bool operator> (const point& a,const point& b)  { 
    //     return a.val > b.val; 
    // }
};
int main() {
    priority_queue<point,vector<point>,greater<point>> pq;
    pq.push(point(1,2,3));
    getchar();
    return 0;
}

【TIP】用priority_queue一个一个插入元素创建堆时间复杂度为O(nlgn),可以直接用priority_queue<int> b(a.begin(),a.end());
该构造函数调用make_heap(),时间复杂度为O(n)。

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐