【C++】优先队列简介与模拟实现 + 仿函数

上文链接

• 【C++】容器适配器 + stack/queue/deque详解

一、优先队列简介

优先队列（priority_queue）不同于普通的先进先出（FIFO）队列，它是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。

优先队列底层其实就是堆，而堆逻辑结构是一个完全二叉树，物理存储上是用数组来实现的。因此我们可以选择使用 vector 或者 deque 来作为它适配的容器。deque 头插头删效率高，但是 vector 的随机访问效率更高，因此 vector 作为适配的容器更为合适。

优先队列默认是一个大根堆。

二、模拟实现（默认大堆）

1. 整体框架

namespace mine
{
	template<class T, class Container = vector<T>>  // 用 vector 作为底层容器
	class priority_queue
	{
	public:
		priority_queue()  // 构造函数
		{}
        
    private:
		Container _con;
	};

}

2. 向上调整算法

当我们向堆中插入数据时，需要使用向上调整算法调整，因为向堆中插入数据是将数据插入到数组中下标为 size 的位置，此时就不一定满足大堆，因此，需要堆其进行调整，向上调整法只需从插入的节点位置开始和父节点比较，若 _con[child] > _con[parent]，则交换，否则说明已经满足大堆，直接 break 。

void adjust_up(size_t child)
{
	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
		if (_con[child] > _con[parent])
		{
			swap(_con[child], _con[parent]);

			// 继续向上比较
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

3. push()

有了向上调整，接下来我们就可以来进行插入操作了。

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

4. 向下调整算法

向下调整算法的核心思想：选出左右孩子中大的那一个，跟父亲交换，大的往上浮，小的往下沉。

void adjust_down(size_t parent)
{
	size_t child = parent * 2 + 1;
	while (child < _con.size())
	{
		// 防止左孩子存在但是右孩子不存在的情况
		if (child + 1 < _con.size() && _con[child + 1] > _con[child])
		{
			++child;
		}
		if (_con[child] > _con[parent])
		{
			swap(_con[child], _con[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

5. pop()

优先队列的删除一定都是删除堆顶（头部）元素，那么有了向下调整，我们只需要把头部元素与尾部元素交换位置，进行尾删操作然后向下调整即可完成删除操作。

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

	adjust_down(0);
}

6. top()

获取优先队列的头部（堆顶）元素，注意这里和栈不同，栈的获取顶部元素有两个版本：一个是普通版本，一个是 const 版本。但是堆中只有 const 版本，因为我们不能随意对堆顶元素进行修改，否则会破坏堆的性质。

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

7. size()

获取优先队列的大小。

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

8. empty()

判断优先队列是否为空，为空返回真。

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

三、仿函数

1. 什么是仿函数

仿函数也叫函数对象，本质上是一个类，这个类可以像函数一样去使用。我们来看这样一个例子：

template<class T>
class Less
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};

template<class T>
class Greater
{
public:
	bool operator()(const T& x, const T& y)
	{
		return x > y;
	}
};


int main()
{
	Less<int> lessFunc;
	cout << lessFunc(1, 2) << endl;

	Greater<int> GreaterFunc;
	cout << GreaterFunc(1, 2) << endl;

	return 0;
}

• 运行结果

1
0

上面实现的这种重载了 () 的 Less 和 Greater 类其实就是仿函数，也叫做函数对象。它们虽然是一个类，但是却可以像函数一样去使用。

2. 仿函数的使用案例

我们学过了基本的排序算法，以简单的插入算法为例，如果我们直接去写的话会发现我们只能够实现单独的升序或降序的其中一种，而在使用的时候往往我们两个都需要。这个时候仿函数就起到了作用：

template<class T, class Compare>
void InsertSort(vector<T>& a, Compare com)
{
	for (int i = 0; i < a.size() - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			// if(tmp > a[end])
			// if(tmp < a[end])
			if (com(tmp, a[end]))
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

int main()
{
	Less<int> LessFunc;
	Greater<int> GreaterFunc;

	vector<int> v = {2, 11, 5, 3, 7, 4, 9, 10};

	InsertSort(v, LessFunc);  // 想排升序，只需传入对应的仿函数即可
	for (auto e : v) cout << e << " ";

	cout << endl;

	InsertSort(v, GreaterFunc);  // 排降序同理
	for (auto e : v) cout << e << " ";

	return 0;
}

• 运行结果

2 3 4 5 7 9 10 11
11 10 9 7 5 4 3 2

3. 仿函数在优先队列中的使用

在优先队列中，默认是大堆，那么如果我们想要使用小堆的话就要用到仿函数了。和上面的插入排序案例的使用方式类似，我们首先需要在优先队列的模板参数列表中添加仿函数的参数 Compare，默认是使用 Less 比较逻辑，与库中一致。

template<class T, class Container = vector<T>, class Compare = Less<T>>

接下来我们可以通过用仿函数替换比较时的逻辑来实现大堆或者小堆。

void adjust_up(size_t child)
{
	Compare com;
	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
		//if (_con[child] > _con[parent])
		if(com(_con[parent], _con[child]))  // 使用仿函数，想要大堆就用 Less，小堆就用 Greater
		{
			swap(_con[child], _con[parent]);

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

void adjust_down(size_t parent)
{
	Compare com;
	size_t child = parent * 2 + 1;
	while (child < _con.size())
	{
		if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))  // 使用仿函数
		{
			++child;
		}
		//if (_con[child] > _con[parent])
		if(com(_con[parent], _con[child]))  // 使用仿函数
		{
			swap(_con[child], _con[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

在使用优先队列时只需指定模板参数即可，传入 Less 或者不传为大堆，传入 Greater 为小堆。

int main()
{
    mine::priority_queue<int, deque<int>, Greater<int>> pq;

	pq.push(1);
	pq.push(11);
	pq.push(10);
	pq.push(50);
	pq.push(32);

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

• 运行结果

1 10 11 32 50