[数据结构与算法]priority_que＜元素类型容器类型比较类型＞自定义比较类型

前言

很早之前接触算法时就遇到了一些题目需要使用优先队列(也是大顶堆和小顶堆)的数据结构,但是对它的初始化和表示的含义一直不太明辨,今天就来说一下最近的理解.希望能够给大家一定的启发.

大顶堆?小顶堆?

为什么叫做大顶堆?因为这个堆的top()函数返回的值就是当前堆的最大值,所以取名叫做大顶堆,同理top()函数返回的是最小值,所以叫做小顶堆.

初始化函数

不知道大家有没有和我一样的感觉,堆的初始化方式及其麻烦,我们先来看看他的初始化方式--

priority_queue<元素类型,适配器类型,比较方式>

元素类型很好理解,可以解释为二叉树节点中保存元素的类型,可以是int,pair...char...等等.

适配器类型是很多人困惑的类型,其实队列底层并不是有固定的实现的数据结构的,这个数据结构我们是可以手动定义的,比如我们手动定义底层实现为vector<元素类型>.

比较方式,这个地方非常容易产生误会--我们接下来看一个例子.

#include<bits/stdc++.h>
using namespace std;

int main(){
    //auto cmp=[](int a,int b){return a<b;};//3 重定义小于号，即less,是大顶堆，即默认的
    auto cmp=[](int a,int b){return a>b;};//1  //重定义大于号，即greater，是小顶堆
    priority_queue<int,vector<int>,decltype(cmp)> pq(cmp);
    pq.push(1);
    pq.push(2);
    pq.push(3);
    cout<<pq.top();
    return 0;
}

例子来源尊重作者,表明出处.

上述例子中,我们定义a<b时,为大顶堆,我们可能会疑惑,明明是小于号,为何叫做大顶堆呢?我是这样理解的,这里的底层调用一定是关于sort()函数的STL库函数,sort函数中 cmp()方式定义为a<b时返回的是升序排列,而升序是后一个元素大于前一个元素的.我们从叶子节点出发向根节点寻觅,每一条支脉也是一个升序数组.(小根堆同理)

自定义比较类型

思路:我们手写一个类,再在这个类里面定义bool operator()(数据类型 1,数据类型2){? 1>2表示小顶堆,1<2表示大顶堆.}

错误代码:

class Solution {
public:
    class MyCompare {
        bool operator()(pair<int, int> f, pair<int, int>s) {
            return f.second > s.second;         //这里是为了定义为小顶堆
        }
    };
    

    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> map;
        priority_queue < pair<int, int>, vector<pair<int, int>>, MyCompare> que;
        for (auto i : nums) {
            map[i]++;
        }
    }
};

注意上述代码是有问题的,因为我们的另一个类内的函数调用了第一个类的operator()比较函数,所以我们呢需要将第一个类中的重定义operator函数记为PUBLIC,不然编译器会报错,说找不到operator()函数. 哎,果然是好事多磨~

正确代码:

//此题目对应的是力扣的"前K个高频元素"一题
class Solution {
public:
    class MyCompare {
        bool operator()(pair<int, int> f, pair<int, int>s) {
            return f.second > s.second;         //这里是为了定义为小顶堆
        }
    };

    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> vec;
        unordered_map<int, int> map;
        priority_queue < pair<int, int>, vector<pair<int, int>>, MyCompare> que;
        for (auto i : nums) {
            map[i]++;
        }
        unordered_map<int, int>::iterator i = map.begin();
        for (; i != map.end(); ++i) {
            que.push(*i);
            if (que.size() > k)
                que.pop();
        }
        while (!que.empty()) {
            vec.push_back(que.top().first);
            que.pop();
        }
        return vec;
    }
};

小结

主要是记住三部分priority_queue<元素类型,适配器类型,比较方式所在类型>,注意比较方式是新建类重写operator(),重新定义比较方式,注意比较方式类型,后面没有加括号!!!

个人理解,欢迎交流.