priority_queue模拟

一、什么是priority_queue?

        priority_queue是C++标准库中的一个容器适配器，用于实现优先队列（priority queue）的数据结构。优先队列是一种特殊的队列，其中的元素按照一定的优先级进行排序，每次取出的元素都是优先级最高的。它的优先级是可以通过传入参数自己调整的，它的底层实现通常使用堆(heap)数据结构。以下是堆结构的学习链接：堆(建堆算法，堆排序)-CSDN博客
主要特点
        元素有序：队列中的元素会根据其优先级进行排序，优先级最高的元素总是位于队列的头部（或称为队首）。
        操作：主要操作包括插入新元素（push）、删除优先级最高的元素（pop）以及访问优先级最高的元素（top，但不删除）。
        默认行为：默认情况下，priority_queue使用最大堆实现，即优先级最高的元素（值最大的元素）存储在根节点。但可以通过指定比较函数来改变元素的排序方式，例如使用std::greater可以实现最小堆，即优先级最低的元素（值最小的元素）存储在根节点。

二、priority_queue如何用？

模板参数

priority_queue的模板定义通常包含三个参数：

• typename T：元素类型。
• typename Container = std::vector<T>：底层容器类型，默认为std::vector<T>。虽然std::deque也满足条件，但std::vector因其高效的随机访问性能而更常被用作底层容器。
• typename Compare = std::less<T>：比较函数类型，用于确定元素的优先级。默认为std::less<T>，表示元素按从大到小的顺序排列；若需按从小到大的顺序排列，可指定为std::greater<T>。

以上是priority_queue的接口函数，该篇文章只来学习和模拟c++11以前的接口。

以下是这些接口的使用：

//使用示例
#include<iostream>
#include<queue>
using namespace std;
//这是自定义优先级的一种格式
template<typename T>
class gt
{
public://如果返回true则b优先，返回false则a优先，所以这里使用gt会生成小堆bool operator()(T a, T b){return a > b;}
private:
};
int main()
{priority_queue<int> heap1;//int表示储存的类型priority_queue<int, vector<int>> heap2;//这里vector表示使用的底层容器，这里也可以换成deque<int>。//greater为编译器提供的类模板，默认的优先级是大堆，而使用它可以生成小堆。priority_queue<int, vector<int>, greater<int>> heap3;//当然也可以自己设计一个优先级方式传入，该方法常常用于储存自定义类型，而内置类型编译器提供的就够用。priority_queue<int, vector<int>, gt<int>> heap4;//push接口用于存入元素heap4.push(2);heap4.push(7);heap4.push(1);heap4.push(5);cout << heap4.size() << endl;//size用于计算队列中元素的个数while (!heap4.empty())//empty用于判断队列是否为空{cout << heap4.top() << ' ';//top获取队头元素heap4.pop();//pop删除队头元素}return 0;
}

以上输出为：

三、priority_queue模拟实现

1.模板参数

       首先为了区别于库里面的优先级队列，我们可以用命名空间限制它的作用域。通过观察库里面的priority_queue模板参数一共有三个，第一个为储存的元素类型，第二个参数为需要用的底层容器（默认为vector），第三个参数为用来调整优先级的类模板（需要我们写一个默认模板），那么我们可以做以下设计：

#include<iostream>
#include<vector>
using namespace std;
namespace byte//用命名空间限制它的作用域，来区别于库里面的优先级队列
{template<typename T, class Container = vector<T>, class Compare = less<T>>class priority_queue{public://...private://...};
}

 注意：这里vector模板我们可以使用库里面的，但优先级队列模板（less<T>）需要我们自己写。

2.成员变量

        STL的任何模拟，如果在考虑成员变量如何设计而发愁，我们可以去想如何储存对象的数据进而来设计我们的成员变量。这里我们用的是容器Container（即vector<int>）来储存数据的，所以我们的成员变量之一类型一定是Container，其次因为想到不同对象传入的Compare可能不同，具有特殊性，所以我们也可以把Compare（优先级调整的类模板）作为成员变量。如下：

private:Container arr;Compare comp;

3.成员函数

        因为在priority_queue模拟中并不涉及到动态内存开辟和一些特殊理，所以这里的构造函数用编译器默认提供的构造函数就够用了，并不需要我们自己编写。

        在优先级队列中因为涉及到堆的调整所以在push和pop接口的设计中有些复杂，其他接口的设计都非常简单就不在讲解，后面大家直接看源码。

3.1.push

        首先需要把arr看做是一个堆结构，无论arr里面有没有元素，然后直接把元素push_back到arr中，此时该元素所在位置为堆底，而且并不一定是正确的位置，接下来要做的就是对该元素进行向上调整。

父子节点的定义：子节点记为child，父节点记为father。

child=arr.size()-1

father=(child-1)/2（理解原理后可以当做公式记忆，可通过一下链接参考学习）

向下调整的方法我在以下文章中有具体讲解：

堆(建堆算法，堆排序)_初始建堆算法-CSDN博客

		void AdjustUP(){int child = arr.size() - 1, father = (child - 1) / 2;while (child > 0){if (comp(arr[father], arr[child])){std::swap(arr[child], arr[father]);child = father;father = (child - 1) / 2;}else{break;}}}

3.2.pop

        该函数主要功能是pop堆顶元素，但是如果直接pop堆顶元素（下标为0）的话，那么下标为1的会成为堆顶元素，会使原来的父子关系和兄弟关系混乱，要重新调整起来极其复杂，所一需要换一种方案，我们可以把堆顶元素与堆底元素交换然后pop堆底元素，然后对堆进行向下调整。

父子节点的定义：子节点记为child，父节点记为father。

father=0

child=father*2+1（这里father和child的计算公式是可以互推的）

向下调整的方法我在以下文章中有具体讲解：

堆(建堆算法，堆排序)_初始建堆算法-CSDN博客

四、源码

#include<iostream>
#include<vector>
using namespace std;
namespace byte
{template<typename T>class less{public://如果返回true则b优先，返回false则a优先，所以这里使用gt会生成小堆bool operator()(T a, T b){return a < b;}private:};template<typename T>class greater{public://如果返回true则b优先，返回false则a优先，所以这里使用gt会生成小堆bool operator()(T a, T b){return a > b;}private:};template<typename T, class Container = vector<T>, class Compare = less<T>>class priority_queue{public:void AdjustUP(){int child = arr.size() - 1, father = (child - 1) / 2;while (child > 0){if (comp(arr[father], arr[child])){std::swap(arr[child], arr[father]);child = father;father = (child - 1) / 2;}else{break;}}}void AdjustDOWN(){int father = 0, child = father * 2 + 1;while (child < arr.size()){if (child + 1 < arr.size() && comp(arr[child], arr[child + 1])){child++;}if (comp(arr[father], arr[child])){std::swap(arr[child], arr[father]);father = child;child = father * 2 + 1;}else{break;}}}void push(T x){arr.push_back(x);AdjustUP();}void pop(){std::swap(arr[0], arr[arr.size() - 1]);arr.pop_back();AdjustDOWN();}T top(){return arr[0];}size_t size(){return arr.size();}bool empty(){return arr.size() == 0;}private:Container arr;Compare comp;};
}