【c++】stl_priority_queue优先级队列

薄荷冰

发布于 2024-01-22 18:43:37

3400

文章被收录于专栏：后端学习之旅后端学习之旅

一、priority_queue的介绍

首先让我们通过阅读优先级队列的官方文档

简单翻译一下

1. 优先队列是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含的元素中最大的。 2. 此上下文类似于堆，在堆中可以随时插入元素，并且只能检索最大堆元素 ( 优先队列中位于顶部的元素) 。 3. 优先队列被实现为容器适配器，容器适配器即将特定容器类封装作为其底层容器类 queue 提供一组特定的成员函数来访问其元素。元素从特定容器的“ 尾部 ” 弹出，其称为优先队列的顶部。 4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作： empty() ：检测容器是否为空 size() ：返回容器中有效元素个数 front() ：返回容器中第一个元素的引用 push_back() ：在容器尾部插入元素 5. 标准容器类 vector 和 deque 满足这些需求。默认情况下，如果没有为特定的 priority_queue 类实例化指定容器类，则使用vector 。 6. 需要支持随机访问迭代器，以便始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、 push_heap 和 pop_heap 来自动完成此操作。

二、 priority_queue的本质

通过阅读优先级队列的模板，我们可以看到priority_queue默认使用vector作为底层的存储数据的容器，然后在vector之上又使用了堆算法将vector中的元素构成堆的结构，因此我们可以认为优先级队列就是堆，所有需要的堆的位置都可以使用 priority_queue（比如：top_k问题）。对于堆来说，大堆还是小堆是十分关键的，让我们将目光看向第三个类模板参数，

Compare = less<typename Container::value_type>

这里的less是类中仿函数的使用，其本质其实就是判断是否小于：

此时我们已经彻底了解了优先级队列的本质，接下来我们开始学习使用该容器：

三、priority_queue的使用

下面我们简单的使用一下上面提到的函数

#include <queue>
#include <iostream>

int main() {
    std::priority_queue<int, std::vector<int>, std::less<int>> pq;

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

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

    return 0;
}

输出结果为：4 3 1 1

在上面的代码中，我们创建了一个存储整数的优先队列pq，并依次插入了4个元素。然后，我们使用top()函数和pop()函数访问和移除元素，最后使用empty()函数检查队列是否为空。

其实我们对于优先级队列的使用就是对于堆的使用。

四、priority_queue的模拟实现

最基础的就是建堆

template <class InputIterator>
priority_queue(InputIterator first, InputIterator last)
{
    while (first != last)
    {
        c.push_back(*first);
        first++;
    }
	for (int i = (c.size() - 2) / 2; i >= 0; i++)//-1是数组下标里面-1，再-1  /2是找    最后一个孩子的爹
	{
        AdjustDown(i);
    }
}

//向下调整
void AdjustDown(int parent)
{
    size_t child = parent * 2 + 1;
    while (child < c.size())
    {
        if (child + 1 < c.size() && comp(c[child], c[child + 1]))child++;//找到最大的左右孩子之一
        if (comp(c[parent], c[child]))
		{
			swap(c[parent], c[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else break;
	}
}
	    Container c;
		Compare comp;

其次就是添加和减少：

	    void push(const T& x)
		{
			c.push_back(x);
			AdjustUp(c.size() - 1);
		}
		void AdjustUp(int child)
		{
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				if(comp(c[parent], c[child]))
				{
					std::swap(c[parent], c[child]);
					child=parent ;
					parent = (child - 1) / 2;
				}
				else break;

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

最后就是其他比较简单的函数

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

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

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