属性和方法

std::priority_queue 是 C++ STL 中的一个容器适配器，它提供了一些基本属性和方法，用于管理基于优先级的队列。以下是 std::priority_queue 的主要属性和方法：

1. 构造函数

默认构造函数：
- std::priority_queue<T>：创建一个空的优先队列，其中 T 是存储的数据类型。
带容器和比较函数的构造函数：
- std::priority_queue<T, Container, Compare>：创建一个指定底层容器和比较方式的优先队列，Container 默认是 std::vector<T>，Compare 默认是 std::less<T>（大顶堆）。

2. 属性

类型定义：
- value_type：存储的元素类型。
- container_type：底层容器的类型（默认为 std::vector<T>）。
- size_type：大小类型，用于存储优先队列中元素个数的数据类型。
- reference：返回元素的引用类型。
- const_reference：返回常量元素的引用类型。

3. 成员方法

3.1 元素访问

top()：
- 功能：返回队列中优先级最高的元素（对于大顶堆是最大元素）。
- 复杂度：O(1)。
- 示例：
  std::priority_queue<int> pq; pq.push(10); pq.push(5); pq.push(20); std::cout << pq.top(); // 输出 20

3.2 容量相关

empty()：
- 功能：检查优先队列是否为空。如果为空，返回 true，否则返回 false。
- 复杂度：O(1)。
- 示例：
  if (pq.empty()) { std::cout << "Queue is empty"; }
size()：
- 功能：返回优先队列中元素的数量。
- 复杂度：O(1)。
- 示例：
  std::cout << "Size: " << pq.size(); // 输出优先队列的元素数量

3.3 修改容器

push(const value_type& val)：
- 功能：将元素 val 插入到优先队列中。
- 复杂度：O(log n)，因为插入后需要维护堆结构。
- 示例：
  pq.push(15); // 插入 15 到优先队列
emplace(Args&&... args)：
- 功能：原位构造一个对象并插入到优先队列中，避免了复制操作。
- 复杂度：O(log n)。
- 示例：
  pq.emplace(25); // 原位构造并插入 25
pop()：
- 功能：移除优先级最高的元素（对于大顶堆是最大元素）。
- 复杂度：O(log n)，因为移除后需要维护堆结构。
- 示例：
  pq.pop(); // 移除优先级最高的元素

3.4 交换内容

swap(priority_queue& other)：

功能：与另一个优先队列 other 交换元素。
复杂度：O(1)。

示例：

std::priority_queue<int> pq1, pq2;
pq1.push(10);
pq2.push(20);
pq1.swap(pq2);  // 交换两个优先队列的内容

4. 比较函数

std::priority_queue 的默认比较方式是 std::less<T>，即大顶堆。如果需要自定义优先级，可以传入自定义的比较器，例如使用 std::greater<T> 实现小顶堆。

示例：使用 std::greater<T> 实现小顶堆

#include <queue>
#include <vector>
#include <iostream>

int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;  // 小顶堆
    pq.push(10);
    pq.push(5);
    pq.push(20);

    std::cout << pq.top();  // 输出 5
}

5. 总结

方法

描述

时间复杂度

top()

返回优先级最高的元素（不移除）。

O(1)

push(const T& val)

插入新元素，并重新调整堆。

O(log n)

emplace(Args&&... args)

原位构造新元素并插入队列。

O(log n)

pop()

移除优先级最高的元素，并重新调整堆。

O(log n)

empty()

检查优先队列是否为空。

O(1)

size()

返回优先队列中的元素数量。

O(1)

swap(priority_queue& other)

交换两个优先队列的内容。

O(1)

std::priority_queue 是一个灵活的容器，适用于需要管理具有优先级的任务或数据的场景，如贪心算法、调度系统等。

Previous优先队列 Next详细内容

Last updated 9 months ago