【C++杂货铺】优先级队列的使用指南与模拟实现

谁践踏了优雅 2023-10-15 17:43 40阅读 0赞

![在这里插入图片描述][70e14bb981db40c9abfeab063db5c9a5.gif_pic_center]

#### **文章目录** ####

*  一、priority\_queue的介绍
 *  二、priority\_queue的使用
 *   *  2.1 数组中的第k个最大元素
 *  三、priority\_queue模拟实现
 *   *  3.1 仿函数
     *  3.2 成员变量
     *  3.3 成员函数
     *   *  3.3.1 构造函数
         *  3.3.2 AdjustDown
         *  3.3.3 push
         *  3.3.4 AdjustUp
         *  3.3.5 pop
         *  3.3.6 empty
         *  3.3.7 size
 *  四、结语

## 一、priority\_queue的介绍 ##

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

## 二、priority\_queue的使用 ##

优先级队列默认使用 vector 作为其底层存储数据的容器，在 vector 上又使用了堆算法将 vector 中元素构造成堆的结构，因此 priority\_queue 就是堆，所有需要用到堆的位置，都可以考虑使用 priority\_queue。注意：默认情况下 priority\_queue 是大堆。

<table> 
 <thead> 
  <tr> 
   <th><b>函数声明</b></th> 
   <th><b>接口说明</b></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>priority_queue()</td> 
   <td>构造一个空的优先级队列</td> 
  </tr> 
  <tr> 
   <td>empty()</td> 
   <td>检测优先级队列是否为空，是返回 true，否则返回 false</td> 
  </tr> 
  <tr> 
   <td>top()</td> 
   <td>返回优先级队列中最大（最小）元素，即堆顶元素</td> 
  </tr> 
  <tr> 
   <td>push(x)</td> 
   <td>在优先级队列中插入元素 x</td> 
  </tr> 
  <tr> 
   <td>pop()</td> 
   <td>删除优先级队列中最大（最下）元素，即堆顶元素</td> 
  </tr> 
 </tbody> 
</table>

**小Tips**：默认情况下，priority\_queue 是大堆（默认第三个模板参数是 less）；如果在 priority\_queue 中放自定义类型的数据，用户需要在自定义类型中提供 > 或者 < 的重载。

### 2.1 数组中的第k个最大元素 ###

![在这里插入图片描述][ec04d03d24154ef383eb7e96123bd917.png_pic_center]

class Solution {
        
    public:
        int findKthLargest(vector<int>& nums, int k) 
        {
        
            //建一个大堆，向下调整建堆的时间复杂度是O（N）
            priority_queue<int> pq(nums.begin(), nums.end());
    
            //pop k-1次,时间复杂度是O(K*logN)
            while(--k)
            {
        
                pq.pop();
            }
    
            return pq.top();
        }
    };

上面这种做法当 K 的值接近 N 的时候，它的时间复杂度就是 O(N\*logN)，是不满足题目要求的，下面再用另外一种方法来解决。

lass Solution {
        
    public:
        int findKthLargest(vector<int>& nums, int k) 
        {
        
            //用前k个数建一个小堆
            priority_queue<int, vector<int>, greater<int>> pq(nums.begin(), nums.begin() + k);
    
            //遍历剩下的 N-k 个，比堆顶大就换进去
            //时间复杂度是 (N-K)logN
            for(size_t i = k; i < nums.size(); i++)
            {
        
                if(nums[i] > pq.top())
                {
        
                    pq.pop();
                    pq.push(nums[i]);
                }
            }
            return pq.top();
        }
    };

上面这种解法是先用数组中的前 K 个元素建一个小堆，然后从数组的第 K+1 个元素开始往后遍历，遇到比堆顶元素大的就将堆顶的元素 pop 出来，将当前元素 push 进去。建堆的时间复杂度是 O(K)，更新小堆的时间复杂度是 O((N-K)logK)，这种做法当 K 很小的时候时间复杂度可以近似看做 O(NlogK)，当 K 很大的时候，时间复杂度可以近似看做 O(logK)。

## 三、priority\_queue模拟实现 ##

### 3.1 仿函数 ###

仿函数本质上一个类，之所以把它叫仿函数是因为这个类的对象可以像函数一样去使用。举例如下：

//一个仿函数
    template<class T>
    class Less
    {
        
    public:
    	bool operator()(const T& x, const T& y)
    	{
        
    		return x < y;
    	}
    };
    
    
    int main()
    {
        
    	Less<int> lessfunc;//定义一个对象
    	cout << lessfunc(1, 2) << endl;//该类型对象可以像函数一样去使用
    	//cout << lessfunc.operator()(1, 2) << endl;//和上面等价
    	return 0;
    }

**小Tips**：仿函数一般都是类模板，这样就可以支持不同类型的大小比较，前提是该种类型重载实现了比较运算符。仿函数的诞生是为了代替函数指针，函数指针的可读性比较差。

### 3.2 成员变量 ###

template<class T, class Container=std::vector<T>, class Compare = Less<T>>
    	class priority_queue
    	{
        
    	public:
    		//成员
    	private:
    		Container _con;
    	};

**小Tips**：需要注意这里有三个模板参数，第一个模板参数表示要在优先级队列中存储的数据类型；优先级队列本质上也是一个容器适配器，所以第二个模板参数表示优先级队列要使用的底层容器；第三个模板参数是一个仿函数，用来进行大小比较的，因为优先级队列中会涉及到建大堆还是建小堆，中间会涉及到比较，如果没有这个仿函数，那么大小比较就只能写死了，这样不太好。

### 3.3 成员函数 ###

#### 3.3.1 构造函数 ####

priority_queue()
    {
        }
    
    template<class InputeIterator>
    priority_queue(InputeIterator first, InputeIterator last)
    {
        
    	//先将数据插入
    	while (first != last)
    	{
        
    		_con.push_back(*first);
    		++first;
    	}
    
    	//建堆,从最后一个非叶子节点开始向下调整
    	for (int i = (_con.size() - 1) / 2; i >= 0; i--)
    	{
        
    		AdjustDown(i);
    	}
    }

**小Tips**：迭代器区间构造函数是一个函数模板，只要是能支持 ++ 操作的迭代器区间都可以，即单向迭代器、双向迭代器、随机迭代都可以。其次将数据插入容器后还需要建堆，这里采用向下调整建堆，它的时间复杂度是 O(N)。

#### 3.3.2 AdjustDown ####

void AdjustDown(int parent)
    {
        
    	Compare com;
    	while (parent * 2 + 1 < (int)_con.size())
    	{
        
    		//找到最大的孩子
    		int maxchild = parent * 2 + 1;
    		if (maxchild + 1 < (int)_con.size() && com(_con[maxchild], _con[maxchild + 1]))
    		{
        
    			maxchild++;
    		}
    
    		//和父节点比较
    		if (com(_con[parent], _con[maxchild]))
    		{
        
    			std::swap(_con[maxchild], _con[parent]);
    			parent = maxchild;
    		}
    		else
    		{
        
    			break;
    		}
    	}
    }

**小Tips**：在仿函数的加持下，向下调整代码中的大小比较不再固定，建大堆和小堆这一份代码就够了，最终是大堆还是小堆是由仿函数来控制的。

#### 3.3.3 push ####

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

**小Tips**：在优先级队列的尾部追加数据，会涉及到向上调整，向上调整的代码如下所示。

#### 3.3.4 AdjustUp ####

void AdjustUp(int child)
    {
        
    	Compare com;
    	int parent = (child - 1) / 2;
    	while (child > 0)//父亲不会小于0，因此这里的判断条件要用孩子大于0，孩子等于0说明已经调整到根节点，就无需继续调整了
    	{
        
    		if (com(_con[parent], _con[child]))
    		{
        
    			std::swap(_con[child], _con[parent]);
    			child = parent;
    			parent = (child - 1) / 2;//这里parent不会小于0
    		}
    		else
    		{
        
    			break;
    		}
    	}
    }

#### 3.3.5 pop ####

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

**小Tips**：优先级队列中出数据，出的是堆顶的数据，堆顶的数据也就是容器中的第一个数据，如果底层容器是 vector 那么堆顶的数据就是下标为 0 的数据，出堆顶的数据不能直接使用头删，这样会导致后面数据的父子关系全乱了。正确的做法是，将堆顶的数据和容器中的最后一个数据交换，然后执行 pop\_back 去删除，最后还需要从根节点开始执行一次向下调整，让交换到堆顶的数据去到它应该去的地方。

#### 3.3.6 empty ####

bool empty()
    {
        
    	return _con.size() == 0;
    }

#### 3.3.7 size ####

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

## 四、结语 ##

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，[春人的主页][Link 1]还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是春人前进的动力！

![在这里插入图片描述][edc78985d03043828f98dcd5a8d2983e.gif_pic_center]

[70e14bb981db40c9abfeab063db5c9a5.gif_pic_center]: https://img-blog.csdnimg.cn/70e14bb981db40c9abfeab063db5c9a5.gif#pic_center
[ec04d03d24154ef383eb7e96123bd917.png_pic_center]: https://img-blog.csdnimg.cn/ec04d03d24154ef383eb7e96123bd917.png#pic_center
[Link 1]: https://blog.csdn.net/weixin_63115236?spm=1000.2115.3001.5343
[edc78985d03043828f98dcd5a8d2983e.gif_pic_center]: https://img-blog.csdnimg.cn/edc78985d03043828f98dcd5a8d2983e.gif#pic_center