前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >C++面试不可不知的优先级队列

C++面试不可不知的优先级队列

作者头像
程序员的园
发布2024-07-18 13:37:53
1270
发布2024-07-18 13:37:53
举报
文章被收录于专栏:程序员的园——原创文章

在C++中,优先级队列(std::priority_queue)是一个功能强大的容器适配器,它基于堆实现,提供了基于元素优先级的快速访问和排序功能。下面,我们将结合代码示例来深入理解std::priority_queue的使用方法和实战技巧。

基本用法

std::priority_queue的基本使用示例如下:

代码语言:javascript
复制
#include <iostream>
#include <queue>


int main() {
// 创建一个整型的最大堆
std::priority_queue<int> pq;

// 添加元素
    pq.push(3);
    pq.push(1);
    pq.push(4);

    // 访问顶部元素
    std::cout << "Top element: " << pq.top() << std::endl; // 输出 4
    // 移除顶部元素
    pq.pop();
    std::cout << "Top element after pop: " << pq.top() << std::endl; // 输出 3


    // 检查队列是否为空
    if (pq.empty()) {
      std::cout << "Queue is empty." << std::endl;
    } 
    else {
      std::cout << "Queue is not empty." << std::endl;
    }


    // 获取队列大小
    std::cout << "Size of queue: " << pq.size() << std::endl; // 输出 2
    return 0;
}

如上示例代码中使用了priority_queue的push、pop、top、empty、size函数,其中:

  • push(const value_type& val): 在队列的尾部添加一个元素。
  • pop(): 移除队列的顶部元素(即优先级最高的元素)。
  • top(): 返回队列的顶部元素的引用,但不移除该元素。
  • empty(): 检查队列是否为空。
  • size(): 返回队列中的元素个数。

自定义比较函数

默认情况下,std::priority_queue使用std::less<T>作为比较函数实现最大堆,其也支持用户指定比较函数,如指定STL内置的比较算法,甚至自定义比较函数

使用内置比较算法

在如上的代码中,指定优先级队列的比较函数为std::greater,构建一个小顶堆,只需修改一行代码,如下:

代码语言:javascript
复制
// 创建一个整型的小顶堆
std::priority_queue<int,std::vector<int>,std::greater<int>> pq;
//其余代码同上例

自定义比较函数

std::priority_queue支持自定义比较函数,示例代码如下:

代码语言:javascript
复制
#include <iostream>
#include <queue>
#include <functional>


struct Person {
  std::string name;
  int age;
public:
    Person(const std::string& n, int a) : name(n), age(a) {}
};


// 自定义比较函数,实现最小堆
struct ComparePerson {
  bool operator()(const Person& p1, const Person& p2) 
{
        return p1.age > p2.age;
  }
};


int main() {
    std::priority_queue<Person, std::vector<Person>, ComparePerson> pq;
    pq.push(Person("Alice", 25));
    pq.push(Person("Bob", 20));
    pq.push(Person("Charlie", 30));
    std::cout << "Top element (youngest person): " \
      << pq.top().name << ", " \
      << pq.top().age << std::endl; // 输出 Charlie, 30
    return 0;
}

改变底层容器

默认情况下,priority_queue使用std::vector作为底层容器。但其支持在构造对象时显示指定其底层容器,如上例中在构造对象pq时指定容器为std::vector<>;也可以使用std::deque或`std::std::list作为底层容器。

代码语言:javascript
复制
//以std::queue作为底层容器
int main() {
  std::priority_queue<int, std::deque<int>, std::less<int>> pq;
  pq.push(3);
  pq.push(1);
  pq.push(4);
  
  
  // 访问顶部元素
  std::cout << "Top element: " << pq.top() << std::endl; // 输出 4
  
  // 移除顶部元素
  pq.pop();
  std::cout << "Top element after pop: " << pq.top() << std::endl; // 输出 3
  return 0;
}

注意:由于priority_queue需要支持随机访问和高效的插入和删除操作,因此并不是所有的容器都适合作为底层容器。

优先级队列的遍历

在C++标准库中std::priority_queue并未直接提供遍历元素的接口,因为它是基于堆实现的,主要优化了插入和顶部元素的取出操作。所以针对优先级队列的遍历需要将值一个个取出来,示例代码如下:

代码语言:javascript
复制
int main() {
  std::priority_queue<int> pq;
  pq.push(20);
  pq.push(15);
  pq.push(30);
  
  while (!pq.empty()) {
  // 理论述逻辑上访问顶部元素,实际STL priority_queue不支持直接遍历
  std::cout << pq.top() << " ";
  // 正常情况下这里无法直接pop后继续遍历,因为会改变pq
  // 这里仅为示意,实际代码中不能如此操作
          pq.pop();
  }
  
  std::cout<<"\n";
  return 0;
}
/*output:
30 20 15


*/

当然将队列中所有的数据取出来放到支持迭代器的数据结构中,但是那已是对应数据结构的特性。

总结

C++的priority_queue是一个功能强大的容器适配器,它基于堆实现,提供了基于元素优先级的快速访问和排序功能。通过自定义比较函数,你可以轻松地改变priority_queue的排序方式。priority_queue虽好,但在选用数据结构要结合应用场景,慎重抉择。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2024-06-03,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序员的园 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
相关产品与服务
容器服务
腾讯云容器服务(Tencent Kubernetes Engine, TKE)基于原生 kubernetes 提供以容器为核心的、高度可扩展的高性能容器管理服务,覆盖 Serverless、边缘计算、分布式云等多种业务部署场景,业内首创单个集群兼容多种计算节点的容器资源管理模式。同时产品作为云原生 Finops 领先布道者,主导开源项目Crane,全面助力客户实现资源优化、成本控制。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档