当前位置:首页 » 《我的小黑屋》 » 正文

C++:priority_queue优先队列

4 人参与  2024年10月31日 13:21  分类 : 《我的小黑屋》  评论

点击全文阅读


文章目录

前言一、优先级队列概念及用法1.1 优先级队列概念1.2 优先级队列的使用1.2.1 对于内置类型1.2.2 对于自定义类型 二、小试牛刀三、优先级队列模拟实现3.1 优先队列模板参数与成员变量3.2 构造相关3.2.1 默认构造3.2.2 迭代器构造3.2.3 使用仿函数优化比较,实现大根堆与小根堆切换 3.3 其他功能实现3.3.1 push函数3.3.2 pop函数3.3.3 top、size和empty函数 四、仿函数4.1 仿函数概念4.2 优先队列中的模拟实现 总代码实现


前言

今天我们一起来学习优先级队列~~~<( ̄︶ ̄)↗[GO!]

在这里插入图片描述


一、优先级队列概念及用法

1.1 优先级队列概念

优先队列是一种特殊的容器适配器,主要依赖堆的结构来保证元素按照特定的顺序进行操作。它的核心功能是确保队列的第一个元素总是最大或最小的元素,具体取决于堆的类型(大顶堆或小顶堆)。

在这里插入图片描述


功能说明
容器适配器优先队列是通过封装标准容器类(如vectordeque)实现的,作为底层数据存储。默认情况下使用vector
类似堆的结构优先队列与堆相似,支持随时插入元素,并且只能访问位于顶部的最大(或最小)元素。
算法支持内部通过自动调用堆算法,如make_heappush_heappop_heap,保持队列的堆结构。
随机访问迭代器容器类应支持随机访问迭代器,如vectordeque,以便操作元素。
元素访问与修改提供empty()size()top()等函数来操作和访问容器中的元素,元素总是从容器的“顶部”弹出。

常用接口与方法

方法功能说明
priority_queue()构造一个空的优先队列。
empty()检测优先队列是否为空,空则返回true,否则返回false
size()返回优先队列中的元素个数。
top()返回优先队列中最大的元素,即堆顶元素。
push(x)向优先队列中插入元素x,并重新调整堆结构。
pop()删除并移除优先队列中的最大元素,即堆顶元素。

优先队列通常使用vector作为底层存储结构,借助堆算法将vector中的元素构造成堆的形式。对于需要频繁使用堆的场景,优先队列是一个非常高效且方便的选择。注意,默认情况下优先队列是大顶堆,即top()返回的是当前最大的元素。


1.2 优先级队列的使用

1.2.1 对于内置类型

大根堆的使用

priority_queue<int> q;// 默认是大根堆,这里其实省略了三个模板参数,写完整是这样的// <优先级队列类型, 底层容器类型, 比较方式> 变量名;// priority_queue<int, vector<int>, less<int>> q;
优先级队列模板参数: int: 队列中存储的数据类型。vector<int>: 底层容器类型,优先队列默认使用vector来存储数据。less<int>: 仿函数,用于定义优先队列的排序方式,默认是less<int>,表示大根堆(最大元素位于堆顶)。

在这里,priority_queue<int>实际上等价于priority_queue<int, vector<int>, less<int>>,即默认情况下优先队列是一个大根堆,也就是每次弹出最大值。

q.push(2);q.push(3);q.push(4);q.push(1);
通过push()方法向优先队列中插入元素,队列会根据大根堆的规则自动调整顺序。插入顺序是2, 3, 4, 1
while (!q.empty()) {    cout << q.top() << " ";    q.pop();}
q.top():返回堆顶元素(当前队列中的最大值)。q.pop():移除堆顶元素,并重新调整堆结构。通过while循环依次输出并弹出堆顶元素,直到队列为空,输出顺序应该为4 3 2 1

创建小根堆

#include // greater算法的头文件

priority_queue<int, vector<int>, greater<int>> q2;// 如果要建小根堆,也就是升序,要更改最后一个模板参数仿函数,也就是改变比较的方式
这里创建了一个小根堆,不同之处在于使用了greater<int>作为仿函数。 greater<int>:与less<int>相反,表示升序排列,即最小元素位于堆顶。
q2.push(2);q2.push(3);q2.push(4);q2.push(1);
同样地,通过push()方法插入元素2, 3, 4, 1,此时优先队列会自动构造成小根堆。
while (!q2.empty()) {    cout << q2.top() << " ";    q2.pop();}
通过while循环依次输出并弹出堆顶元素,直到队列为空,输出顺序应该为1 2 3 4

总结

大根堆:默认情况下,priority_queue使用less<int>作为仿函数,即构建大根堆,每次弹出的是最大值。小根堆:通过指定greater<int>作为仿函数,可以构建小根堆,优先队列会自动将最小元素置于堆顶。

这里用deque也可以,不过我们在调整建堆是需要大量的随机访问,deque这方面是比较不行的,因此推荐适配器用vector就可以了。
在这里插入图片描述


这里还可以用迭代器区间来构造优先级队列。

void test_priority_queue02(){vector<int> v = { 1, 3, 5 ,2 ,9 };priority_queue<int> q(v.begin(), v.end());while (!q.empty()){cout << q.top() << " ";q.pop();}cout << endl;}

1.2.2 对于自定义类型

如果在priority_queue中放自定义类型的数据,用户需要在自定义类型中提供> 或者< 的重载。
在这里插入图片描述


我们建议再自定义类型的内部进行operator<以及operator>,如果遇到实在无法再类内重载这些的情况,比如我传进来的日期类是一对指针,可以用一下的方法操作。

priority_queue<Date*, vector<Date*>, LessDate<Date*>> q;
priority_queue<Date*, vector<Date*>, LessDate<Date*>>:构造了一个存储Date*类型的优先队列,并使用LessDate仿函数来进行排序。

使用自定义仿函数来处理指针类型(如Date*)的优先队列排序。默认情况下,priority_queue无法直接比较指针类型,因此需要通过自定义的仿函数LessDate来实现指针的解引用与比较。

template<class T>class LessDate {public:    bool operator()(const Date* pd1, const Date* pd2) const {        // 解引用指针并比较Date对象        return *pd1 < *pd2;    }};
LessDate:这是一个仿函数,用于比较Date*类型的指针,内部通过解引用指针来比较Date对象的大小。重载operator():定义了比较逻辑,仿函数在优先队列中用于排序。

在这里插入图片描述


二、小试牛刀

数组中的第K个最大元素
在这里插入图片描述

class Solution {public:    int findKthLargest(vector<int>& nums, int k)     {        priority_queue<int> q(nums.begin(), nums.end());        for (int i = 0; i < k - 1; i++) q.pop();        return q.top();    }};

三、优先级队列模拟实现

3.1 优先队列模板参数与成员变量

通过上面的使用我们可以发现,优先队列需要三个模板参数

class T //类型, class Container = vector //适配器
class compare = less//仿函数用于建堆调整比较

而它的成员变量自然就是这个适配器

template<class T, class Container = vector<T>, class compare = less<T>>class priority_queue{public:private:Container _con;};

3.2 构造相关

3.2.1 默认构造

默认构造,对于自定义类型,会去调_con的构造函数
priority_queue() {}

3.2.2 迭代器构造

template<class Iterator>priority_queue(Iterator first, Iterator last) {    while (first != last) {        _con.push_back(*first);        ++first;    }    // 向下调整建堆    for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--) {        AdjustDown(i);    }}

建堆主逻辑

通过迭代器范围[first, last)将元素添加到底层容器_con中。每个元素都被依次插入到容器中。在所有元素都插入后,接下来需要将这些元素调整为堆结构。通过对非叶子节点进行向下调整(调用AdjustDown),从最后一个非叶子节点开始,依次调整直到根节点。

向下调整

向下调整的主要逻辑在AdjustDown函数中实现。其主要目标是保持堆的性质(大根堆),具体步骤如下: 从父节点开始,计算其左子节点的位置。比较父节点与子节点(及其兄弟节点)的值,找到更大的子节点。如果父节点小于最大子节点,则交换二者,并继续向下调整。直到满足堆的性质(即父节点大于或等于子节点)为止。

时间复杂度分析

建堆的时间复杂度:在构造函数中,插入元素的时间复杂度为O(n),因为每个元素都需要被添加到底层容器中。向下调整的时间复杂度AdjustDown的时间复杂度为O(log n),每次调用会最多经过树的高度(log n)进行比较和交换。由于我们需要从每个非叶子节点向下调整,整体建堆的复杂度为O(n)。

在这里插入图片描述

private://向下调整建堆void AdjustDown(int parent){int child = parent * 2 + 1;while (child < _con.size()){// 我们要排大根堆,降序排列,因此要找孩子中大的那一个if (child + 1 < _con.size() && _con[child] < _con[child + 1])child++;if (_con[parent] < _con[child]){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}elsebreak;}}public://默认构造,对于自定义类型,会去调_con的构造函数priority_queue() {}//支持迭代器//迭代器也要写成模板template<class Iterator>priority_queue(Iterator first, Iterator last){while (first != last){_con.push_back(*first);++first;}//向下调整建堆for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){AdjustDown(i);}}

3.2.3 使用仿函数优化比较,实现大根堆与小根堆切换

在前面的代码中,我们直接将比较的方法写死了。
在这里插入图片描述

如果我们要实现小根堆呢?要重新再写一个函数吗?

答案是不用,我们可以使用一个仿函数,重新定义比较,传什么仿函数就用什么比较。

这里要注意的是,因为我们仿函数代表的仅仅是一种<>,因此我们再写的时候要把符号关系搞成一致,像这样:
在这里插入图片描述

//向下调整建堆void AdjustDown(int parent){//仿函数定义一个对象出来,用它来替换比较Compare com;int child = parent * 2 + 1;while (child < _con.size()){// 我们要排大根堆,降序排列,因此要找孩子中大的那一个if (child + 1 < _con.size() && com(_con[child] , _con[child + 1]))child++;if (com(_con[parent] , _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}elsebreak;}}

3.3 其他功能实现

3.3.1 push函数

void push(const T& x) {    _con.push_back(x);    AdjustUp(_con.size() - 1);}
功能:将新元素x插入到优先队列中。过程: 首先将元素x添加到容器_con的尾部。然后调用AdjustUp函数,从新插入元素的位置向上调整,确保堆的性质被保持(大根堆)。

3.3.2 pop函数

void pop() {    swap(_con[0], _con[_con.size() - 1]);    _con.pop_back();    AdjustDown(0);}
功能:删除优先队列中优先级最高的元素(堆顶元素)。过程: 先将堆顶元素(即_con[0])与堆尾元素交换。删除堆尾元素。通过调用AdjustDown函数,从堆顶开始向下调整,保持堆的性质。

3.3.3 top、size和empty函数

top:返回堆顶元素,即优先队列中优先级最高的元素。size:返回优先队列中元素的数量。empty:检查优先队列是否为空。

向上调整 (AdjustUp)

//向上调整void AdjustUp(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}elsebreak;}}
功能:调整刚插入的元素,使堆满足大根堆性质。过程: 计算当前元素的父节点位置。在while循环中,如果子节点的值大于父节点的值,则进行交换。更新childparent的值,继续向上调整,直到不再需要交换或达到根节点。

四、仿函数

4.1 仿函数概念

仿函数(Functor)是一个重载了 operator() 的类或结构体,能够像函数一样被调用。它们常用于需要自定义比较、处理或操作的数据结构和算法中,比如在 STL 容器、算法中作为参数传递。

仿函数的优势在于:

可以持有状态:仿函数的对象可以保存数据,允许使用构造函数初始化。语义明确:通过命名类,能够清晰表达意图。

以下是一个简单的仿函数例子:

#include <iostream>using namespace std;// 定义一个仿函数类class Compare {public:    // 重载运算符()    bool operator()(int a, int b) const {        return a < b; // 返回true表示a小于b    }};int main() {    Compare compare;    int x = 5, y = 10;    // 使用仿函数进行比较    if (compare(x, y)) {        cout << x << " is less than " << y << endl;    } else {        cout << x << " is not less than " << y << endl;    }    return 0;}

输出

5 is less than 10

Compare 类实现了一个仿函数,通过重载 operator() 来比较两个整数。通过创建 Compare对象并调用它,就可以像使用普通函数一样进行比较。


4.2 优先队列中的模拟实现

//仿函数模拟实现/函数对象template<class T>class Less{public:bool operator() (const T& a, const T& b){return a < b;}};template<class T>class Greater{public:bool operator() (const T& a, const T& b){return a > b;}};

总代码实现

以下是优先队列中大根堆和小根堆的对应关系,以及根节点的最大和最小属性:

堆类型比较方式仿函数根节点
大根堆>std::less<T>最大
小根堆<std::greater<T>最小
#pragma once#include<vector>namespace jyf{//仿函数模拟实现/函数对象template<class T>class Less{public:bool operator() (const T& a, const T& b){return a < b;}};template<class T>class Greater{public:bool operator() (const T& a, const T& b){return a > b;}};template<class T, class Container = vector<T>, class Compare = less<T>>class priority_queue{private://向下调整void AdjustDown(int parent){//仿函数定义一个对象出来,用它来替换比较Compare com;int child = parent * 2 + 1;while (child < _con.size()){// 我们要排大根堆,降序排列,因此要找孩子中大的那一个if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))child++;if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}elsebreak;}}//向上调整void AdjustUp(int child){Compare com;int parent = (child - 1) / 2;while (child > 0){if (com(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}elsebreak;}}public://默认构造,对于自定义类型,会去调_con的构造函数priority_queue() {}//支持迭代器//迭代器也要写成模板template<class Iterator>priority_queue(Iterator first, Iterator last){while (first != last){_con.push_back(*first);++first;}//向下调整建堆for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--){AdjustDown(i);}}void push(const T& x){//先放到堆尾_con.push_back(x);//进行向上调整AdjustUp(_con.size() - 1);}void pop(){//先交换第一个和最后一个swap(_con[0], _con[_con.size() - 1]);//删除堆尾_con.pop_back();//向下调整AdjustDown(0);}const T& top(){return _con[0];}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};void test_priority_queue1(){// 默认是大堆 -- less//priority_queue<int> pq;// 仿函数控制实现小堆priority_queue<int, vector<int>, Greater<int>> pq;pq.push(3);pq.push(5);pq.push(1);pq.push(4);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;}}

到这里就结束啦,谢谢大家!!!??????○( ^皿^)っHiahiahia…

在这里插入图片描述


点击全文阅读


本文链接:http://zhangshiyu.com/post/180470.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

关于我们 | 我要投稿 | 免责申明

Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1