c++中priority_queue模拟的实现

目录

• 一、什么是priority_queue?
• 二、priority_queue如何用？
• 三、priority_queue模拟实现
• 1.模板参数
• 2.成员变量
• 3.成员函数
• 3.1.push
• 3.2.pop
• 四、源码

一、什么是priority_queue?

priority_queue是C++标准库中的一个容器适配器，用于实现优先队列（priority queue）的数据结构。优先队列是一种特殊的队列，其中的元素按照一定的优先级进行排序，每次取出的元素都是优先级最高的。它的优先级是可以通过传入参数自己调整的，它的底层实现通常使用堆(heap)数据结构。以下是堆结构的学习链接：堆(建堆算法，堆排序)

主要特点

• 元素有序：队列中的元素会根据其优先级进行排序，优先级最高的元素总是位于队列的头部（或称为队首）。
• 操作：主要操作包括插入新元素（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.pus编程客栈h(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的任何模拟，如果在考虑成员变量如何设计而发愁，我们可以去想如何储存对象的数据进而来设计我们的成员变量。这里我们用的是容器Containewww.devze.comr（即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（理解原理后可以当做公式记忆，可通过一下链接参考学习）

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

堆(建堆算法，堆排序)_初始建堆算法

3.2.pop

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

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

father=0

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

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

堆(建堆算法，堆排序)_初始建堆算法

四、源码

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

到此这篇关于c++中priority_queue模拟的实现的文章就介绍到这了,更多相关c++ priority_queue模拟内容请搜索编程客栈(www.devze.com)以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程客栈(www.devze.com)！