目录

前言

1、优先队列使用简介

2、优先队列内部原理

2.1 优先队列的容器

2.2 优先队列的数据类型

2.3 优先队列比较类型

3、基于二叉堆的优先队列操作

3.1 top

3.2 push

3.3 adjust_heap（堆维护）

结语

前言

这一次的内容是手动实现priority_queue 

priority_queue参考Microsoft visual studio2022文档priority_queue 类 | Microsoft Docs

 关于对堆排序和二叉堆的介绍，强烈推荐这个视频排序算法：堆排序【图解+代码】_哔哩哔哩_bilibili

priority_queue即是优先队列，包含在内

1、优先队列使用简介

原型：

template ,// base container,default:std::vector
class Compare= less >
//比较方式，如果是less则是大根堆
//每次输出的元素都是优先队列中的最大值
//default:std::less
class priority_queue

众所周知，优先队列每次输出的都是优先级最大的元素，优先级是可以自己定义的，默认是输出最大值，例如：

#include
//#include"queue.h"
#include
#include
using std::endl;
using std::cout;
int main() {
	std::vector nums{ 1,1,4,5,1,4 };
	std::priority_queue q(nums.begin(), nums.end());
	cout << q.top() << endl;
	q.pop();
	cout << q.top() << endl;
}

输出结果都是最大值

这里我们可以尝试更换一下比较方式：

这里我不得不吐槽一下，个人觉得比较方式应该设置为第二个模板参数，因为中间的模板参数基础容器一般是没人回去改的，而如果你要更改比较方式，就不得不为了占位置，把中间的参数也填上

#include
//#include"queue.h"
#include
#include
using std::endl;
using std::cout;
int main() {
	std::vector nums{ 1,1,4,5,1,4 };
	std::priority_queue,
std::greater> q(nums.begin(), nums.end());
//设置基础容器是vector，设置比较方式是greater，也就是大于
	cout << q.top() << endl;
	q.pop();
	cout << q.top() << endl;
}

再次查看输出结果，输出了两个1 

这里就出现了一个很离谱的设定，明明是less但是每次弹出的都是最大值，明明是greater，却每次出来的都是最小值，这个问题，涉及到priority_queue的底层原理。

2、优先队列内部原理

优先队列可以用一个二叉堆来维护，这样每次取值都只需要花O(1)的时间取堆顶元素花O(logn)的时间维护堆，取最大值就维护一个大顶堆，取最小值就维护一个小顶堆。关于堆的原理，参考本文最初提到的视频连接，堆排序是数据结构里面需要掌握的内容，不论是B站还是CSDN都有数不胜数的教程。后面的内容需要理解堆排序和二叉堆的原理。

2.1 优先队列的容器

优先队列的默认容器是vector，vector是一种在末尾插入和删除时间为O(1)其他位置插入和删除时间为O(n)的支持随机访问的容器

根据堆的原理，也需要在末尾进行插入和删除，并且需要随机访问

作为优先队列的基础数据结构，vector是够用的，也可以用deque，链表只能顺序访问，不能支持堆排序所用到的操作，因此不能使用链表

2.2 优先队列的数据类型

优先队列的数据类型必须是可比较的。具体地，比如我现在自定义了一个结构体complex：

struct  complex {
	int x, y;
};
int main() {
	//std::vector nums{ 1,1,4,5,1,4 };
	std::priority_queue q;
	q.push({ 1,2 });
    //其余代码和上面插入的测试代码相同

}

运行会报这个错误：

 因此需要重载小于运算符

struct  complex {
	int x, y;
    
    //修改结构体内部，重载小于运算符
	friend bool operator<(const complex& a, const complex& b);
};
bool operator<(const complex& a, const complex& b) {
	if (a.x == b.x) {
		return a.y < b.y;
	}
	return a.x < b.x;
}

这里我尝试了成员函数重载和友元函数重载，实际结果表示，重载为成员函数依然会报错，因此建议重载为友元函数，本身二元运算符也建议重载为友元函数，因为重载为成员函数时当我们使用operator重载运算符时，左侧的操作数应该是调用对象，这限制了该运算符的使用方式。

2.3 优先队列比较类型

比较类型默认值是std::less，输出默认是最大值，因此可以手动修改，这里介绍两种方式，一种是简单的使用std::greater，另一种则是自己写一个函数类，即重载了()运算符的对象。众所周知，重载了()运算符的对象都是函数对象

//首先写一个类，并且重载()运算符
template
class MyGreater {
public:
	bool operator()(const Type& a, const Type& b) {
		return a > b;
	}
};
//然后再complex类中重载>运算符
//类中声明friend bool operator>(const complex& a, const complex& b);

bool operator>(const complex& a, const complex& b) {
	if (a.x == b.x) {
		return a.y > b.y;
	}
	return a.x > b.x;
}

主函数中调用：

int main() {
	//std::vector nums{ 1,1,4,5,1,4 };
	std::priority_queue, MyGreater> q;
	complex c1(1, 2);
	complex c2(2, 3);
	q.push(c1);
	q.push({ 2,3 });
	auto [x,y]=q.top();//c++17
	cout << x << " " << y << endl;
}

输出结果可以看到输出了较小的那一个complex 

所以到这里就可以发现那个很坑的问题了，C++的优先队列，如果使用less，那么每次输出的是最大值，如果使用greater，每次输出的是最小值，因为使用less，那么维护的是大根堆，反之则是维护的小根堆

3、基于二叉堆的优先队列操作

二叉堆的原理这里不细说了，只需要知道在二叉堆的内部是一个可随机访问的顺序容器，容器内部第一个值就是堆顶元素。

3.1 top

因此如果要取优先队列的top，可以直接返回容器的第一个元素：

template 
Type& priority_queue::top() {
	return Con[0];
}

template 
const Type& priority_queue::top()const {
	return Con[0];
}
//前面一堆模板参数其实都不太需要管，这里的Con是一个随机访问顺序容器，可以是vector
//可以是deque或者是什么其他支持随机访问，末尾插入和删除的顺序容器

接下来是pop操作，pop操作需要删除堆顶元素，众所周知，每一趟堆排序的过程就是先把堆顶元素和容器末尾元素交换，然后再删除容器末尾元素，最后再从顶到底维护一次堆。

template 
void priority_queue::pop() {
	size_t s = Con.size() - 1;
	swap(Con[0], Con[s]);
	Con.pop_back();
	adjust_heap(0, Compare());
    //这里的compare()是用一个重载了括号运算符的类生成一个函数对象的实例
    //传递的参数是比较的方式
    //如果小于，则维护的堆是大根堆，反之是小根堆
}

3.2 push

接下来是push操作，因为我个人理解在容器首部插入和容器尾部插入差别不是特别大，在容器首部插入的话就自顶向下维护一次堆，在容器尾部插入就自底向上维护一次堆。但是vector首部插入特别慢，所以为了泛用一点，统一为尾部插入比较好。

详情看代码注释部分，也能理解为什么less出来的是小根堆

template 
void priority_queue::push(const Type& right) {
	Con.emplace_back(right); //先把元素直接放在容器尾部
	size_t s = Con.size();
	size_t now = s - 1;
	Compare cmp = Compare(); //生成一个函数对象的实例
	while (now) {//当 当前节点不是根节点
		size_t parent = now / 2;
		if (cmp(Con[parent], Con[now])) {//可以借助函数指针来理解。
            //如果传入的参数是std::less
            //那么这条语句就变成
            //if(Con[parent] < Con[now])
            //即是如果父亲小于孩子则交换
            //反复下去最大的元素会上浮到堆顶
			swap(Con[parent], Con[now]);
			now = parent;
		}
		else {
			break;
            //当遇到不需要交换的时候，即是上浮到正确的位置
            //就可以停止上浮了
		}
	}
}

3.3 adjust_heap（堆维护）

最后详细讲一下前面提到的维护堆：adjust_heap

template 
void priority_queue::adjust_heap(size_t root, const Compare& cmp) {
	size_t left = root * 2 + 1;//找作儿子
	size_t right = root * 2 + 2;//找右儿子
	size_t len = Con.size();
	size_t large = root; //记录一个值来寻找父亲和两个儿子之中最大或是最小的那个
	if (left < len && cmp(Con[large], Con[left])) {
        //cmp的解释同上
        //可带入if(Con[large] < Con[left]),std::less建大根堆
        //if(Con[large] > Con[left]),std::greater建小根堆
		large = left;
	}
	if (right < len && cmp(Con[large], Con[right])) {
		large = right;
	}
    //如果父亲节点的值不能作为堆顶元素
	if (large != root) {
		swap(Con[root], Con[large]); //将堆顶元素放在父亲节点
		adjust_heap(large, cmp);//从交换的位置开始自顶向下维护堆
	}
}

看到这里，可以简单的概括一下，再建堆的时候，如果使用std::less，即是如果 小于 则 交换。这个小于是父亲小于儿子，所以是把儿子的值给父亲，因此父亲节点是二叉堆堆里面任意一个子二叉堆的最大值，所以最终建立出来的就是大根堆，内部源码实现其实可以改变比较顺序，改成儿子小于父亲，那么这样less建出来的就是小根堆。

结语

出于晚上的实验课过早完成实验，于是决定写一个篇blog打发时间，顺手记录自己实现优先队列的过程，本来是打算从构造函数到二叉堆，写一篇完整的优先队列实现全过程，但这样写篇幅会非常非常大，于是省去了很多细节，很多解释直接放在代码注释中了，并且还有四十分钟就下课了，再展开过多可能写不完，

如果有错误的地方，欢迎各位大佬提出意见，现在的我完完全全就是一个菜菜，出现错误也是情理之中。