优先级队列的实现

目录

简介

仿函数介绍

使用优先级队列

实现

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_each, std::transform, std::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相关接口