当前位置: 首页> 房产> 建筑 > 优先级队列的实现

优先级队列的实现

时间:2025/7/9 7:10:37来源:https://blog.csdn.net/2302_80190394/article/details/141713662 浏览次数:0次

目录

简介

仿函数介绍

使用优先级队列

实现

Compare仿函数的实现

主体部分


简介

优先级队列(Priority Queue)是一种抽象数据类型,它类似于队列或栈,但是每个元素都关联有一个优先级或权重。在优先级队列中,元素按照优先级的高低来排列,而不是按照它们进入队列的先后顺序。它包含在<queue>这个头文件中。

以下是优先级队列的一些基本特性:

  1. 优先级:每个元素都有一个与之相关的优先级,通常是一个数值,也可能是一个比较复杂的计算结果。优先级决定了元素在队列中的位置。

  2. 基本操作

    • 插入:将元素插入优先级队列中,根据元素的优先级将其置于合适的位置。
    • 删除:通常删除具有最高优先级的元素(在最小优先级队列中则是最低优先级的元素),这个操作也被称为“取出”或“弹出”。
    • 查看最高(或最低)优先级元素:可以查看队列中优先级最高或最低的元素,但不删除它。
  3. 实现方式:优先级队列可以用多种方式实现,如二叉堆(最常见)、平衡二叉搜索树(如AVL树)、斐波那契堆等。

  4. 应用:优先级队列在计算机科学中应用广泛,如作业调度、事件模拟、图算法(如Dijkstra算法和Prim算法)、数据压缩等。

优先级队列的操作时间复杂度通常依赖于所采用的数据结构。例如,使用二叉堆实现的优先级队列,插入和删除操作的时间复杂度通常是O(log n)(堆都是logn),其中n是队列中元素的数量。

这是官网对于优先级队列的解释

可以看出来,这是一个容器适配器,既然是容器适配器,就没有迭代器的相关说法(因为出数据的方式取决于该数据结构的特点)。它默认使用vector适配生成。

本质上,优先级队列就是C语言中的堆。

堆确实是一种特殊的二叉树,具体来说,它是一种完全二叉树。在完全二叉树中,除了最后一层外,每一层的节点都是满的,且最后一层的节点从左到右依次填充。堆的特点是树中的每个父节点的值都小于或大于其子节点的值,具体取决于它是最大堆还是最小堆。因此,堆是一种特殊的二叉树,但并不是所有的二叉树都是堆。

它可以获取堆顶的元素进行入与出。

仿函数介绍

仿函数(Functor)是C++编程语言中的一个概念,它指的是一种具有函数特性的对象。具体来说,仿函数是一个类,这个类重载了函数调用运算符 operator(),使得它可以像函数一样被调用,同时可以拥有状态和数据。

为什么需要介绍仿函数呢?是因为优先级队列的模板中使用了仿函数,仿函数又叫做函数对象。

以下是仿函数的一些特点和用途:

  1. 状态保留:与普通函数不同,仿函数可以拥有自己的状态(即成员变量),这些状态在仿函数的调用之间可以保持不变。

  2. 行为定制:通过继承和重载,仿函数可以在不同的上下文中表现出不同的行为。

  3. 在STL中的使用:在C++的标准模板库(STL)中,很多算法都可以接受一个仿函数作为参数,以此来定制算法的行为。例如,std::sort 可以接受一个比较函数来决定元素的排序顺序。

例子:

#include <iostream>class Adder {
public:Adder(int n) : num(n) {} // 构造函数,初始化状态int operator()(int x) const { return x + num; } // 重载函数调用运算符
private:int num;
};int main() {Adder add5(5); // 创建一个仿函数对象,状态为5std::cout << add5(10) << std::endl; // 调用仿函数,输出15return 0;
}

在这个例子中,Adder 是一个仿函数类,它有一个成员变量 num 用来保存状态,operator() 被重载用来接收一个参数并返回这个参数与 num 的和。

仿函数在C++中广泛应用于算法的定制,特别是在STL中,比如 std::for_eachstd::transformstd::remove_if 等算法都可以使用仿函数来指定特定的操作。

具体仿函数的介绍,将在下面优先级队列的实现阶段进行讲解。

使用优先级队列

这是优先级队列的重要的接口函数,包括插入、删除、、、、、

#include <queue>
#include <iostream>
#include <vector>
using namespace std;int main()
{//priority_queue<int, vector<int>, greater<int>> pq;priority_queue<int> pq;pq.push(1);pq.push(2);pq.push(5);pq.push(6);pq.push(3);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;return 0;
}

可以看到,优先级队列将高优先级的数据(大数)先pop掉了。

这是为什么呢?

因为这里的缺省仿函数是less对象,

这是less的定义,可以看到他是一个模板类,内部的比较规则就是less。所以数据是递减的。

当我们专用greater对象之后,内部数据将会递增


int main()
{priority_queue<int, vector<int>, greater<int>> pq;//priority_queue<int> pq;pq.push(1);pq.push(2);pq.push(5);pq.push(6);pq.push(3);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;return 0;
}

实现

优先级队列是通过模板实现的,有三个模板参数:数据类型、容器、Compare仿函数

Compare仿函数的实现

我们知道,仿函数其实是一个类对象,仿函数的实现就是仿函数类的实现


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;}
};

内部对operator()操作符进行了重载

主体部分

成员变量

Container _con;

我们通过容器来实现优先级队列

向上、向下调整算法

这个算法主要是为了进行建堆操作,满足pop与push接口

调整沿着亲情线进行

void Adjust_Down(size_t parent)
{size_t child = parent * 2 + 1;Compare com;while (child < _con.size()){if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){++child;}if (com(_con[parent], _con[child]))	//左操作数child,右操作数parent{std::swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}elsebreak;	//前提其他已经满足是一个堆结构}}void Adjust_Up(size_t child)
{size_t parent = (child - 1) / 2;	//size_t类型特别注意数组越界Compare com;while (child > 0)	//只要child不是根节点,就得继续上浮(父、子类型都是size_t){if (com(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}elsebreak;}
}

/*
防止数组越界:在堆的调整过程中,child索引是用来追踪当前节点位置的,
而parent索引是通过(child - 1) / 2计算得到的。
如果child等于0,那么parent将会是-1(因为(0 - 1) / 2在整数除法中等于-0.5,
然后被转换为size_t类型,即无符号整数,
结果会是size_t能表示的最大值),这将会导致数组访问越界。
*/

由于this指针隐藏,因此我们只需要传入节点的位置即可

构造函数

我们实现了默认构造与迭代器构造。

其中默认构造会在初始化列表阶段调用容器的默认构造函数

	priority_queue()	//提供默认构造{}

迭代器构造则是给容器提供迭代器构造。然后在内部进行向上调整建堆即可。

采用模板实现,这是因为只要支持随机迭代器的容器,都允许进行数据的构造。

template<class InputIterator>priority_queue(InputIterator first, InputIterator last):_con(first, last)		//容器都有迭代器初始化的方式{for (size_t i = (_con.size() - 2) / 2; i >= 0; --i)	//向下调整,传入根的位置{Adjust_Down(i);		//类内函数,可以隐藏this}}

剩下的pop、push、、、则是调用容器对应的函数

void push(const T& x){_con.push_back(x);Adjust_Up(_con.size() - 1);	//传入下标}void pop(){std::swap(_con[0], _con[_con.size() - 1]);	//【】可以访问,也可以修改_con.pop_back();Adjust_Down(0);}const T& top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}

其中

1.push必须进行向上调整建堆

2.pop必须先首位交换,然后pop,再向下建堆

关于堆的算法

在算法库中,提供了关于建堆、判断、pop、push相关接口

关键字:优先级队列的实现

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: