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

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

一、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 是大堆。

函数声明 接口说明
priority_queue() 构造一个空的优先级队列
empty() 检测优先级队列是否为空,是返回 true,否则返回 false
top() 返回优先级队列中最大(最小)元素,即堆顶元素
push(x) 在优先级队列中插入元素 x
pop() 删除优先级队列中最大(最下)元素,即堆顶元素

小Tips:默认情况下,priority_queue 是大堆(默认第三个模板参数是 less);如果在 priority_queue 中放自定义类型的数据,用户需要在自定义类型中提供 > 或者 < 的重载。

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

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();
}

四、结语

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


目录
相关文章
|
6月前
|
算法 C语言 C++
C++ std::chrono库使用指南 (实现C++ 获取日期,时间戳,计时等功能)(一)
C++ std::chrono库使用指南 (实现C++ 获取日期,时间戳,计时等功能)
2416 1
|
6月前
|
缓存 算法 安全
C++ std::chrono库使用指南 (实现C++ 获取日期,时间戳,计时等功能)(三)
C++ std::chrono库使用指南 (实现C++ 获取日期,时间戳,计时等功能)
334 1
|
1月前
|
存储 算法 调度
【C++打怪之路Lv11】-- stack、queue和优先级队列
【C++打怪之路Lv11】-- stack、queue和优先级队列
34 1
|
6月前
|
安全 调度 C++
C++ std::chrono库使用指南 (实现C++ 获取日期,时间戳,计时等功能)(二)
C++ std::chrono库使用指南 (实现C++ 获取日期,时间戳,计时等功能)
730 0
|
4月前
|
存储 算法 Java
【C++】优先级队列priority_queue模拟实现&&仿函数
【C++】优先级队列priority_queue模拟实现&&仿函数
38 1
|
4月前
|
存储 算法 C语言
【C++】详解STL的适配器容器之一:优先级队列 priority_queue
【C++】详解STL的适配器容器之一:优先级队列 priority_queue
|
6月前
|
存储 算法 C语言
从C语言到C++_19(容器适配器+stack和queue模拟实现+优先级队列priority_queue)(下)
从C语言到C++_19(容器适配器+stack和queue模拟实现+优先级队列priority_queue)
54 2
|
6月前
|
算法 C语言 C++
从C语言到C++_20(仿函数+优先级队列priority_queue的模拟实现+反向迭代器)(上)
从C语言到C++_20(仿函数+优先级队列priority_queue的模拟实现+反向迭代器)
50 1
|
5月前
|
C++ 容器
【c++】优先级队列|反向迭代器(vector|list)
【c++】优先级队列|反向迭代器(vector|list)
38 0
|
6月前
|
算法 C语言 C++
从C语言到C++_20(仿函数+优先级队列priority_queue的模拟实现+反向迭代器)(下)
从C语言到C++_20(仿函数+优先级队列priority_queue的模拟实现+反向迭代器)
29 0
从C语言到C++_20(仿函数+优先级队列priority_queue的模拟实现+反向迭代器)(下)