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

2024-07-18 13:37:53 浏览数 (2)

在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虽好,但在选用数据结构要结合应用场景,慎重抉择。

0 人点赞