备案控制台
开发者社区 开发与运维 文章 正文

【C++】优先级队列 priority_queue的使用及模拟实现@STL —— 仿函数

2022-07-29 105
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 优先级队列也是一种容器适配器，默认情况下它适配的是vector，以支持堆的算法中频繁的随机访问。priority_queue不像stack & queue的适配只是简单复用，还搭配了堆的算法。那么，如何控制大堆还是小堆呢？就要通过简单的**仿函数**啦。let's go!

@toc
优先级队列也是一种容器适配器，默认情况下它适配的是vector，以支持堆的算法中频繁的随机访问。priority_queue不像stack & queue的适配只是简单复用，还搭配了堆的算法。那么，如何控制大堆还是小堆呢？就要通过简单的仿函数啦。let's go!

正文开始

反爬链接

1. 优先级队列的使用

头文件：<queue>

<img src=" title="">

  • Container：默认情况下，它适配的是vector。理论上，底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类，但是必须支持随机访问迭代器访问，以及一系列基本接口。
  • Compare：默认情况下，大的优先级高(即默认是大堆)，仿函数给的是less(这确实有点奇怪)。小堆需要传入仿函数类型，它的头文件在<functional>中。
#include<iostream>
#include<queue>
#include<functional> //greater算法头文件

using namespace std;

int main()
{
    //priority_queue<int> pq; //默认大的优先级高，仿函数为less
    priority_queue<int,vector<int>,greater<int>> pq;

    pq.push(1);
    pq.push(3);
    pq.push(5);
    pq.push(2);
    pq.push(4);
    
    // 适配容器都不能迭代器遍历，因为这样不能保证堆的性质。
    while (!pq.empty())
    {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
    return 0;
}

来一道小题：215. 数组中的第K个最大元素 - 力扣（LeetCode） (leetcode-cn.com)

:purple_heart: 方法一：排序

时间复杂度：O(N*logN)

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        return nums[nums.size()-k]; //倒数第k个
    }
};

或排升序

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end(),greater<int>());//注意，传的是匿名 对象
        return nums[k-1];
    }
};

:purple_heart: 方法二：建大堆(堆排) + pop (k-1)次取堆顶

时间复杂度：O(N+k*logN)

空间复杂度：O(N) :scream:

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> maxHeap(nums.begin(), nums.end());
        while(--k)
        {
            maxHeap.pop();
        }
        return maxHeap.top();
    }
};
  • 注意：迭代器区间构造，即建堆。不需要遍历push了

如果N>>k，法1和法2的代价太大，我们借鉴topK问题的思路，建一个k个数的小堆 ——

:purple_heart: 方法三：建一个k个数的小堆 + 取堆顶元素

时间复杂度：O(k+(N-k)*logk)

空间复杂度：O(k)

时间复杂度和法二相差不大，但空间消耗最小，是这道题目的极致写法。

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        //小堆
        priority_queue<int, vector<int>, greater<int>> minHeap(nums.begin(), nums.begin()+k);
        for(int i = k; i<nums.size(); i++)
        {
            if(nums[i]>minHeap.top())
            {
                minHeap.pop();
                minHeap.push(nums[i]);
            }
        }
        return minHeap.top();
    }
};

2. priority_queue的模拟实现

priority_queue框架，它的底层是一个随机容器。模板参数的第三个参数(仿函数)后面详谈——

template<class T,class Container = vector<T>,class Compare = less<T>>
class priority_queue
{
private:
    void ajust_up(size_t child);
    void ajust_down(size_t parent);

public:
    priority_queue()
    {}

    void push(const T& x);
    void pop();

    const T& top() const;
    size_t size() const;
    bool empty() const;

private:
    Container _con;
};

2.1 size & empty & top

一系列简单接口。top是取堆顶元素。

    const T& top() const
    {
        return _con[0];
    }

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

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

2.2 仿函数

我们写一个类，没有任何成员变量，重载() ——

    template<class T>
    struct Less
    {
        bool operator()(const T& x, const T& y)
        {
            return x < y;
        }
    };

    template<class T>
    struct Greater
    {
        bool operator()(const T& x, const T& y)
        {
            return x > y;
        }
    };

不同仿函数类型的对象，用()来调用对应的函数比较方式，就实现了像函数一样调用 ——

// Less<T> - 仿函数类型，less 仿函数对象
int main()
{
    Less<int> less;
    cout << less(1, 2) << endl;
    cout << less.operator()(1, 2) << endl; // 等价于
    
    cout << Less<int>()(1, 2) << endl; //匿名对象

    Greater<int> greater;
    cout << greater(1, 2) << endl;
    cout << greater.operator()(1, 2) << endl;// 等价于
    
    cout << Greater<int>()(1, 2) << endl; //匿名对象

    return 0;
}

建大堆还是建小堆本质是由于ajust_up和ajust_down中的比较符号不同，那么就要通过仿函数来控制。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-72nz857y-1649750293911)(C:\Users\13136\AppData\Roaming\Typora\typora-user-images\image-20220412155308474.png)]

2.2.1 push & 向上调整算法

优先级队列的插入及删除，就是在堆的基础上做插入删除，堆的算法我们都相当熟悉了。

堆插 = 尾插 + 向上调整

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

:purple_heart: 向上调整算法

<img src=" title="">

    void ajust_up(size_t child)
    {
        while (child > 0)
        {
            size_t parent = (child - 1) / 2;
            //if (_con[parent] < _con[child])
            if (Compare()(_con[parent], _con[child]))
            {
                swap(_con[parent], _con[child]);
                child = parent;
            }
            else
            {
                break;
            }
        }
    }

2.2.2 pop & 向下调整算法

堆删 = 交换 + 再删(直接头删会破坏树的关系) + 向下调整(刚好符合左右都是大/小堆的条件)

    void pop()
    {
        swap(_con[0], _con[_con.size() - 1]);
        _con.pop_back();
        ajust_down(0);
    }

:purple_heart: 向下调整算法

<img src=" title="">

    void ajust_down(size_t parent)
    {
        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() && Compare()(_con[child], _con[child + 1]))
                child++;

            //if (_con[parent],<_con[child])
            if (Compare()(_con[parent], _con[child]))
            {
                swap(_con[parent], _con[child]);
                parent = child;
                child = parent * 2 + 1;
            }
            else
            {
                break; 
            }
        }
    }

向上调整和向下调整算法我们都把它实现成私有，因为不太希望别人直接调用。

2.3 构造函数

:purple_heart: 迭代器区间构造：_con自定义类型会调用它的迭代器区间构造，不用再迭代器遍历+push了。但在这基础上，还需要构建成堆，为了使左右都是大(小)堆，要倒着建，从最后一个非叶子节点(即最后一个节点的父亲)开始向下调整。

    public:
        priority_queue()
        {}

        template<class InputIterator>
        priority_queue(InputIterator first, InputIterator last)
            : _con(first,last)
        {
            //构建堆结构
            for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
            {
                ajust_down(i);
            }
        }

2.4 关于T是自定义类型

我们考虑，当T是自定义类型(比如Date)时 ——

    void test_priority_queue2()
    {
        //priority_queue<Date> pq;
        priority_queue<Date, vector<Date>, greater<Date>> pq;
        pq.push(Date(2022, 3, 26));
        pq.push(Date(2022, 4, 1));
        pq.push(Date(2022, 2, 19));
        pq.push(Date(2022, 4, 10));

        while (!pq.empty())
        {
            cout << pq.top() << endl;
            pq.pop();
        }
    }

在仿函数中，<和>运算符是无法直接比较的。of course 我们可以重载运算符like this ——

    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);
    private:
        int _year;
        int _month;
        int _day;
    };

    ostream& operator<<(ostream& _cout, const Date& d)
    {
        _cout << d._year << "-" << d._month << "-" << d._day;
        return _cout;
    }

但是如果数据类型 不支持比较 或 比较的方式不是你想要的，可以自己实现仿函数，按照你想要的方式(Compare给我们留的口子)去控制比较逻辑，比如 ——

    void test_priority_queue3()
    {
        //priority_queue<Date*> pq; //默认比较地址大小
        //priority_queue<Date*, vector<Date*>, lessPDate> pq;
        priority_queue<Date*, vector<Date*>, greaterPDate> pq;
        pq.push(new Date(2022, 3, 26));
        pq.push(new Date(2022, 4, 1));
        pq.push(new Date(2022, 2, 19));
        pq.push(new Date(2022, 4, 10));

        //默认比较地址大小，若想比较日期大小，自己写仿函数
        while (!pq.empty())
        {
            cout << *pq.top() << endl;
            pq.pop();
        }
    }

于是我们自己写了仿函数，又因为私有成员类外无法访问，我们把这两个仿函数类声明为priority_queue的友元类 ——

    struct lessPDate
    {
        bool operator()(const Date* d1,const Date* d2)
        {
            //return *d1 < *d2;
            return (d1->_year < d2->_year) ||
                (d1->_year == d2->_year && d1->_month < d2->_month) ||
                (d1->_year == d2->_year && d1->_month == d2->_month && d1->_day < d2->_day);
        }
    };

    struct greaterPDate
    {
        bool operator()(const Date* d1, const Date* d2)
        {
            //return *d1 > *d2;
            return (d1->_year > d2->_year) ||
                (d1->_year == d2->_year && d1->_month > d2->_month) ||
                (d1->_year == d2->_year && d1->_month == d2->_month && d1->_day > d2->_day);
        }
    };

附：priority_queue.h

如果你被东一块儿西一块儿的代码搞晕了哈哈，欢迎通读.h文件 ——

#pragma once
#include<iostream>
#include<vector>

using namespace std;

namespace beatles
{
    template<class T>
    struct less
    { 
        // 大堆
        bool operator()(const T& x, const T& y)
        {
            return x < y;
        }
    };

    template<class T>
    struct greater
    {
        // 小堆
        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
    {
    private:
        void ajust_up(size_t child)
        {
            while (child > 0)
            {
                size_t parent = (child - 1) / 2;
                //if (_con[parent] < _con[child]) //默认大堆的情况下
                if (Compare()(_con[parent], _con[child]))
                {
                    swap(_con[parent], _con[child]);
                    child = parent;
                }
                else
                {
                    break;
                }
            }
        }

        void ajust_down(size_t parent)
        {
            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() && Compare()(_con[child], _con[child + 1]))
                    child++;

                //if (_con[parent],<_con[child]) //默认大堆的情况下
                if (Compare()(_con[parent], _con[child]))
                {
                    swap(_con[parent], _con[child]);
                    parent = child;
                    child = parent * 2 + 1;
                }
                else
                {
                    break; 
                }
            }
        }

    public:
        priority_queue()
        {}

        template<class InputIterator>
        priority_queue(InputIterator first, InputIterator last)
            : _con(first,last)
        {
            //构建堆结构
            for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
            {
                ajust_down(i);
            }
        }

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

        void pop()
        {
            swap(_con[0], _con[_con.size() - 1]);
            _con.pop_back();
            ajust_down(0);
        }

        const T& top() const
        {
            return _con[0];
        }

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

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

    private:
        Container _con;
    };

    // 测试尾插尾删，同时测试了向上调整&向下调整算法
    void test_priority_queue1()
    {
        //priority_queue<int> pq; //默认大的优先级高，仿函数为less
        priority_queue<int, vector<int>, greater<int>> pq;

        pq.push(1);
        pq.push(3);
        pq.push(5);
        pq.push(2);
        pq.push(4);

        while (!pq.empty())
        {
            cout << pq.top() << " ";
            pq.pop();
        }
        cout << endl;
    }

    class Date
    {
        friend struct lessPDate;
        friend struct greaterPDate;

    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);
    private:
        int _year;
        int _month;
        int _day;
    };

    ostream& operator<<(ostream& _cout, const Date& d)
    {
        _cout << d._year << "-" << d._month << "-" << d._day;
        return _cout;
    }

    // 对于自定义类型，可以重载>和<
    // 如果数据类型不支持比较 或 比较的方式不是你想要的
    // 可以自己实现 仿函数，按照你想要的方式去控制比较逻辑
    void test_priority_queue2()
    {
        //priority_queue<Date> pq;
        priority_queue<Date, vector<Date>, greater<Date>> pq;
        pq.push(Date(2022, 3, 26));
        pq.push(Date(2022, 4, 1));
        pq.push(Date(2022, 2, 19));
        pq.push(Date(2022, 4, 10));

        while (!pq.empty())
        {
            cout << pq.top() << endl;
            pq.pop();
        }
    }

    struct lessPDate
    {
        bool operator()(const Date* d1,const Date* d2)
        {
            //return *d1 < *d2;
            return (d1->_year < d2->_year) ||
                (d1->_year == d2->_year && d1->_month < d2->_month) ||
                (d1->_year == d2->_year && d1->_month == d2->_month && d1->_day < d2->_day);
        }
    };

    struct greaterPDate
    {
        bool operator()(const Date* d1, const Date* d2)
        {
            //return *d1 > *d2;
            return (d1->_year > d2->_year) ||
                (d1->_year == d2->_year && d1->_month > d2->_month) ||
                (d1->_year == d2->_year && d1->_month == d2->_month && d1->_day > d2->_day);
        }
    };

    void test_priority_queue3()
    {
        //priority_queue<Date*> pq; //默认比较地址大小
        //priority_queue<Date*, vector<Date*>, lessPDate> pq;
        priority_queue<Date*, vector<Date*>, greaterPDate> pq;
        pq.push(new Date(2022, 3, 26));
        pq.push(new Date(2022, 4, 1));
        pq.push(new Date(2022, 2, 19));
        pq.push(new Date(2022, 4, 10));

        //默认比较地址大小，若想比较日期大小，自己写仿函数
        while (!pq.empty())
        {
            cout << *pq.top() << endl;
            pq.pop();
        }
    }
    
}

持续更新@边通书

文章标签：
C++
Go
容器
算法
关键词：
C++优先级队列priority_queue
C++优先级队列
C++ priority_queue
C++仿函数
C++优先级队列仿函数
@浮光掠影
目录
相关文章
Eternity._
|
18天前
|
算法 安全 编译器
【C++进阶】模板进阶与仿函数：C++编程中的泛型与函数式编程思想
【C++进阶】模板进阶与仿函数：C++编程中的泛型与函数式编程思想
Eternity._
25 1
东洛的克莱斯韦克
|
1天前
|
存储 算法 C语言
【C++】详解STL的适配器容器之一：优先级队列 priority_queue
【C++】详解STL的适配器容器之一：优先级队列 priority_queue
东洛的克莱斯韦克
8 0
嘎嘎旺
|
6天前
|
C++ 容器
【c++】优先级队列|反向迭代器（vector|list）
【c++】优先级队列|反向迭代器（vector|list）
嘎嘎旺
5 0
米诺斯
|
7天前
|
C++
C++函数对象(仿函数)
C++函数对象(仿函数)
米诺斯
8 0
枫叶丹4
|
7天前
|
存储 设计模式 算法
【C++航海王：追寻罗杰的编程之路】priority_queue(优先队列) | 容器适配器你知道哪些？
【C++航海王：追寻罗杰的编程之路】priority_queue(优先队列) | 容器适配器你知道哪些？
枫叶丹4
22 0
lge101058
|
7天前
|
C++ 容器
【C++】学习笔记——优先级队列
【C++】学习笔记——优先级队列
lge101058
6 0
GR鲸鱼
|
2月前
|
算法 C语言 C++
从C语言到C++_20(仿函数+优先级队列priority_queue的模拟实现+反向迭代器)（下）
从C语言到C++_20(仿函数+优先级队列priority_queue的模拟实现+反向迭代器)
GR鲸鱼
13 0
从C语言到C++_20(仿函数+优先级队列priority_queue的模拟实现+反向迭代器)（下）
ForcibleBugMaker
|
4天前
|
C++
【C++】日期类Date（详解）②
- `-=`通过复用`+=`实现，`Date operator-(int day)`则通过创建副本并调用`-=`。 - 前置`++`和后置`++`同样使用重载，类似地，前置`--`和后置`--`也复用了`+=`和`-=1`。 - 比较运算符重载如`&gt;`, `==`, `&lt;`, `&lt;=`, `!=`，通常只需实现两个，其他可通过复合逻辑得出。 - `Date`减`Date`返回天数，通过迭代较小日期直到与较大日期相等，记录步数和符号。 ``` 这是236个字符的摘要，符合240字符以内的要求，涵盖了日期类中运算符重载的主要实现。
ForcibleBugMaker
11 4
米诺斯
|
7天前
|
C++
C++职工管理系统（类继承、文件、指针操作、中文乱码解决）
C++职工管理系统（类继承、文件、指针操作、中文乱码解决）
米诺斯
10 0
C++职工管理系统（类继承、文件、指针操作、中文乱码解决）
东洛的克莱斯韦克
|
1天前
|
编译器 C语言 C++
【C++】详解string类
【C++】详解string类
东洛的克莱斯韦克
7 0