C++：priority_queue优先队列

前言

今天我们一起来学习优先级队列~~~<(￣︶￣)↗[GO!]

一、优先级队列概念及用法

1.1 优先级队列概念

优先队列是一种特殊的容器适配器，主要依赖堆的结构来保证元素按照特定的顺序进行操作。它的核心功能是确保队列的第一个元素总是最大或最小的元素，具体取决于堆的类型（大顶堆或小顶堆）。

常用接口与方法

优先队列通常使用vector作为底层存储结构，借助堆算法将vector中的元素构造成堆的形式。对于需要频繁使用堆的场景，优先队列是一个非常高效且方便的选择。注意，默认情况下优先队列是大顶堆，即top()返回的是当前最大的元素。

1.2 优先级队列的使用

1.2.1 对于内置类型

大根堆的使用

priority_queue<int> q;
// 默认是大根堆，这里其实省略了三个模板参数，写完整是这样的
// <优先级队列类型, 底层容器类型, 比较方式> 变量名;
// priority_queue<int, vector<int>, less<int>> q;

• 优先级队列模板参数：
  • int: 队列中存储的数据类型。
  • vector<int>: 底层容器类型，优先队列默认使用vector来存储数据。
  • less<int>: 仿函数，用于定义优先队列的排序方式，默认是less<int>，表示大根堆（最大元素位于堆顶）。

在这里，priority_queue<int>实际上等价于priority_queue<int, vector<int>, less<int>>，即默认情况下优先队列是一个大根堆，也就是每次弹出最大值。

q.push(2);
q.push(3);
q.push(4);
q.push(1);

• 通过push()方法向优先队列中插入元素，队列会根据大根堆的规则自动调整顺序。插入顺序是2, 3, 4, 1。

while (!q.empty()) {
    cout << q.top() << " ";
    q.pop();
}

• q.top()：返回堆顶元素（当前队列中的最大值）。
• q.pop()：移除堆顶元素，并重新调整堆结构。
• 通过while循环依次输出并弹出堆顶元素，直到队列为空，输出顺序应该为4 3 2 1。

创建小根堆

#include // greater算法的头文件

priority_queue<int, vector<int>, greater<int>> q2;
// 如果要建小根堆，也就是升序，要更改最后一个模板参数仿函数，也就是改变比较的方式

• 这里创建了一个小根堆，不同之处在于使用了greater<int>作为仿函数。
  • greater<int>：与less<int>相反，表示升序排列，即最小元素位于堆顶。

q2.push(2);
q2.push(3);
q2.push(4);
q2.push(1);

• 同样地，通过push()方法插入元素2, 3, 4, 1，此时优先队列会自动构造成小根堆。

while (!q2.empty()) {
    cout << q2.top() << " ";
    q2.pop();
}

• 通过while循环依次输出并弹出堆顶元素，直到队列为空，输出顺序应该为1 2 3 4。

总结

• 大根堆：默认情况下，priority_queue使用less<int>作为仿函数，即构建大根堆，每次弹出的是最大值。
• 小根堆：通过指定greater<int>作为仿函数，可以构建小根堆，优先队列会自动将最小元素置于堆顶。

这里用deque也可以，不过我们在调整建堆是需要大量的随机访问，deque这方面是比较不行的，因此推荐适配器用vector就可以了。

这里还可以用迭代器区间来构造优先级队列。

void test_priority_queue02()
{
	vector<int> v = { 1, 3, 5 ,2 ,9 };
	priority_queue<int> q(v.begin(), v.end());
	while (!q.empty())
	{
		cout << q.top() << " ";
		q.pop();
	}
	cout << endl;
}

1.2.2 对于自定义类型

如果在priority_queue中放自定义类型的数据，用户需要在自定义类型中提供> 或者< 的重载。

我们建议再自定义类型的内部进行operator<以及operator>，如果遇到实在无法再类内重载这些的情况，比如我传进来的日期类是一对指针，可以用一下的方法操作。

priority_queue<Date*, vector<Date*>, LessDate<Date*>> q;

• priority_queue<Date*, vector<Date*>, LessDate<Date*>>：构造了一个存储Date*类型的优先队列，并使用LessDate仿函数来进行排序。

使用自定义仿函数来处理指针类型（如Date*）的优先队列排序。默认情况下，priority_queue无法直接比较指针类型，因此需要通过自定义的仿函数LessDate来实现指针的解引用与比较。

template<class T>
class LessDate {
public:
    bool operator()(const Date* pd1, const Date* pd2) const {
        // 解引用指针并比较Date对象
        return *pd1 < *pd2;
    }
};

• LessDate类：这是一个仿函数，用于比较Date*类型的指针，内部通过解引用指针来比较Date对象的大小。
• 重载operator()：定义了比较逻辑，仿函数在优先队列中用于排序。

二、小试牛刀

数组中的第K个最大元素

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) 
    {
        priority_queue<int> q(nums.begin(), nums.end());
        for (int i = 0; i < k - 1; i++) q.pop();
        return q.top();
    }
};

三、优先级队列模拟实现

3.1 优先队列模板参数与成员变量

通过上面的使用我们可以发现，优先队列需要三个模板参数

class T //类型, class Container = vector //适配器
class compare = less//仿函数用于建堆调整比较

而它的成员变量自然就是这个适配器

template<class T, class Container = vector<T>, class compare = less<T>>
class priority_queue
{
public:

private:
	Container _con;
};

3.2 构造相关

3.2.1 默认构造

• 默认构造，对于自定义类型，会去调_con的构造函数

priority_queue() {}

3.2.2 迭代器构造

template<class Iterator>
priority_queue(Iterator first, Iterator last) {
    while (first != last) {
        _con.push_back(*first);
        ++first;
    }

    // 向下调整建堆
    for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--) {
        AdjustDown(i);
    }
}

建堆主逻辑

• 通过迭代器范围[first, last)将元素添加到底层容器_con中。每个元素都被依次插入到容器中。
• 在所有元素都插入后，接下来需要将这些元素调整为堆结构。通过对非叶子节点进行向下调整（调用AdjustDown），从最后一个非叶子节点开始，依次调整直到根节点。

向下调整

• 向下调整的主要逻辑在AdjustDown函数中实现。其主要目标是保持堆的性质（大根堆），具体步骤如下：
  • 从父节点开始，计算其左子节点的位置。
  • 比较父节点与子节点（及其兄弟节点）的值，找到更大的子节点。
  • 如果父节点小于最大子节点，则交换二者，并继续向下调整。
  • 直到满足堆的性质（即父节点大于或等于子节点）为止。

时间复杂度分析

• 建堆的时间复杂度：在构造函数中，插入元素的时间复杂度为O(n)，因为每个元素都需要被添加到底层容器中。
• 向下调整的时间复杂度：AdjustDown的时间复杂度为O(log n)，每次调用会最多经过树的高度（log n）进行比较和交换。由于我们需要从每个非叶子节点向下调整，整体建堆的复杂度为O(n)。

private:
	//向下调整建堆
	void AdjustDown(int parent)
	{
		int child = parent * 2 + 1;
		
		while (child < _con.size())
		{
			// 我们要排大根堆，降序排列，因此要找孩子中大的那一个
			if (child + 1 < _con.size() && _con[child] < _con[child + 1])
				child++;

			if (_con[parent] < _con[child])
			{
				swap(_con[parent], _con[child]);
				parent = child;
				child = parent * 2 + 1;
			}
			else
				break;
		}
	}

public:

	//默认构造，对于自定义类型，会去调_con的构造函数
	priority_queue() {}

	//支持迭代器
	//迭代器也要写成模板
	template<class Iterator>
	priority_queue(Iterator first, Iterator last)
	{
		while (first != last)
		{
			_con.push_back(*first);
			++first;
		}

		//向下调整建堆
		for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
		{
			AdjustDown(i);
		}
	}

3.2.3 使用仿函数优化比较，实现大根堆与小根堆切换

在前面的代码中，我们直接将比较的方法写死了。

如果我们要实现小根堆呢？要重新再写一个函数吗？

答案是不用，我们可以使用一个仿函数，重新定义比较，传什么仿函数就用什么比较。

这里要注意的是，因为我们仿函数代表的仅仅是一种<或>，因此我们再写的时候要把符号关系搞成一致，像这样：

//向下调整建堆
void AdjustDown(int parent)
{
	//仿函数定义一个对象出来，用它来替换比较
	Compare com;

	int child = parent * 2 + 1;
	
	while (child < _con.size())
	{
		// 我们要排大根堆，降序排列，因此要找孩子中大的那一个
		if (child + 1 < _con.size() && com(_con[child] , _con[child + 1]))
			child++;

		if (com(_con[parent] , _con[child]))
		{
			swap(_con[parent], _con[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}

3.3 其他功能实现

3.3.1 push函数

void push(const T& x) {
    _con.push_back(x);
    AdjustUp(_con.size() - 1);
}

• 功能：将新元素x插入到优先队列中。
• 过程：
  1. 首先将元素x添加到容器_con的尾部。
  2. 然后调用AdjustUp函数，从新插入元素的位置向上调整，确保堆的性质被保持（大根堆）。

3.3.2 pop函数

void pop() {
    swap(_con[0], _con[_con.size() - 1]);
    _con.pop_back();
    AdjustDown(0);
}

• 功能：删除优先队列中优先级最高的元素（堆顶元素）。
• 过程：
  1. 先将堆顶元素（即_con[0]）与堆尾元素交换。
  2. 删除堆尾元素。
  3. 通过调用AdjustDown函数，从堆顶开始向下调整，保持堆的性质。

3.3.3 top、size和empty函数

• top：返回堆顶元素，即优先队列中优先级最高的元素。
• size：返回优先队列中元素的数量。
• empty：检查优先队列是否为空。

向上调整 (AdjustUp)

//向上调整
void AdjustUp(int child)
{
	Compare com;
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (com(_con[parent], _con[child]))
		{
			swap(_con[parent], _con[child]);

			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}

• 功能：调整刚插入的元素，使堆满足大根堆性质。
• 过程：
  1. 计算当前元素的父节点位置。
  2. 在while循环中，如果子节点的值大于父节点的值，则进行交换。
  3. 更新child和parent的值，继续向上调整，直到不再需要交换或达到根节点。

四、仿函数

4.1 仿函数概念

仿函数（Functor）是一个重载了 operator() 的类或结构体，能够像函数一样被调用。它们常用于需要自定义比较、处理或操作的数据结构和算法中，比如在 STL 容器、算法中作为参数传递。

仿函数的优势在于：

• 可以持有状态：仿函数的对象可以保存数据，允许使用构造函数初始化。
• 语义明确：通过命名类，能够清晰表达意图。

以下是一个简单的仿函数例子:

#include <iostream>
using namespace std;

// 定义一个仿函数类
class Compare {
public:
    // 重载运算符()
    bool operator()(int a, int b) const {
        return a < b; // 返回true表示a小于b
    }
};

int main() {
    Compare compare;

    int x = 5, y = 10;

    // 使用仿函数进行比较
    if (compare(x, y)) {
        cout << x << " is less than " << y << endl;
    } else {
        cout << x << " is not less than " << y << endl;
    }

    return 0;
}

输出

5 is less than 10

Compare 类实现了一个仿函数，通过重载 operator() 来比较两个整数。通过创建 Compare 的对象并调用它，就可以像使用普通函数一样进行比较。

4.2 优先队列中的模拟实现

//仿函数模拟实现/函数对象
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;
	}
};

总代码实现

以下是优先队列中大根堆和小根堆的对应关系，以及根节点的最大和最小属性：

#pragma once
#include<vector>

namespace jyf
{
	//仿函数模拟实现/函数对象
	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;
		}
	};

	template<class T, class Container = vector<T>, class Compare = less<T>>
	class priority_queue
	{
	private:
		//向下调整
		void AdjustDown(int parent)
		{
			//仿函数定义一个对象出来，用它来替换比较
			Compare com;

			int child = parent * 2 + 1;

			while (child < _con.size())
			{
				// 我们要排大根堆，降序排列，因此要找孩子中大的那一个
				if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
					child++;

				if (com(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
					break;
			}
		}

		//向上调整
		void AdjustUp(int child)
		{
			Compare com;
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				if (com(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);

					child = parent;
					parent = (child - 1) / 2;
				}
				else
					break;
			}
		}

	public:

		//默认构造，对于自定义类型，会去调_con的构造函数
		priority_queue() {}

		//支持迭代器
		//迭代器也要写成模板
		template<class Iterator>
		priority_queue(Iterator first, Iterator last)
		{
			while (first != last)
			{
				_con.push_back(*first);
				++first;
			}

			//向下调整建堆
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
			{
				AdjustDown(i);
			}
		}

		void push(const T& x)
		{
			//先放到堆尾
			_con.push_back(x);
			//进行向上调整
			AdjustUp(_con.size() - 1);
		}

		void pop()
		{
			//先交换第一个和最后一个
			swap(_con[0], _con[_con.size() - 1]);
			//删除堆尾
			_con.pop_back();

			//向下调整
			AdjustDown(0);
		}

		const T& top()
		{
			return _con[0];
		}

		size_t size()
		{
			return _con.size();
		}

		bool empty()
		{
			return _con.empty();
		}

	private:
		Container _con;
	};

	void test_priority_queue1()
	{
		// 默认是大堆 -- less
		//priority_queue<int> pq;

		// 仿函数控制实现小堆
		priority_queue<int, vector<int>, Greater<int>> pq;

		pq.push(3);
		pq.push(5);
		pq.push(1);
		pq.push(4);

		while (!pq.empty())
		{
			cout << pq.top() << " ";
			pq.pop();
		}
		cout << endl;
	}
}

到这里就结束啦，谢谢大家!!!💕💕💕😍😍😍○( ＾皿＾)っHiahiahia…