【C/C++ 数据结构 优先队列】了解学习`std::priority_queue`的使用

简介: 【C/C++ 数据结构 优先队列】了解学习`std::priority_queue`的使用

std::priority_queue 是在 C++98 标准中引入的。C++98 是第一个官方批准的 C++ 标准,它在很大程度上奠定了 C++ 语言的基础,并引入了 STL(Standard Template Library),STL 包括了一系列标准的模板类和函数,用于处理数据结构和算法操作。

std::priority_queue 是 STL 的一部分,作为一种容器适配器,它提供了对优先队列这种数据结构的支持。自从 C++98 标准之后,std::priority_queue 一直是 C++ 标准库的一部分,并在后续的 C++ 标准中得到保留和维护。

1. std::priority_queue 的构造方式

std::priority_queue 在 C++ 标准库中提供了几种不同的构造方式。这些构造方法允许你创建一个优先队列,并根据需要自定义底层容器和比较函数。下面是 std::priority_queue 的几种主要构造方法:

1. 默认构造函数

这是最常用的构造函数,它创建一个空的优先队列。默认情况下,底层容器是 std::vector,比较函数是 std::less<T>,其中 T 是存储在优先队列中的元素类型。

std::priority_queue<int> pq;

2. 使用自定义比较函数

此构造函数允许你使用自定义的比较函数。例如,你可以使用 std::greater<T> 来创建一个最小堆。

std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

3. 从范围构造

这个构造函数允许你从一个现有范围(例如另一个容器)中创建一个优先队列。你需要提供开始和结束迭代器,以及可选的比较函数和容器。

std::vector<int> vec = {1, 2, 3, 4, 5};
std::priority_queue<int> pq(vec.begin(), vec.end());

4. 使用自定义底层容器和比较函数

你可以指定一个自定义的底层容器和比较函数。这允许完全控制优先队列的行为。

std::priority_queue<int, std::deque<int>, std::greater<int>> customPQ;

注意事项

  • 在使用从范围构造的构造函数时,优先队列会使用提供的迭代器范围中的元素来初始化,并根据比较函数建立堆的属性。
  • 自定义比较函数应该是一个能够确定两个元素优先级的二元谓词。
  • 自定义底层容器需要支持 front(), push_back(), pop_back() 以及随机访问迭代器。

通过这些不同的构造方法,std::priority_queue 提供了很大的灵活性,使得它可以适应各种不同的使用场景。

2. std::priority_queue 的push和pop

std::priority_queue 是 C++ 标准库中的一个容器适配器,用于提供优先队列的功能。它基于某种底层容器(默认是 std::vector)和一个比较函数(默认是 std::less,意味着元素将按最大值优先的顺序排列)。在 std::priority_queue 中,最大(或根据比较函数确定的“最高优先级”)的元素总是位于队列的前面。

插入(push

  • 用法:void push(const T& value);void push(T&& value);
  • 描述:将一个新元素添加到优先队列中。新元素被放置在优先队列的末尾,然后根据其优先级进行上浮,以确保队列的顶部总是具有最高优先级的元素。
  • 复杂度:通常是对数时间,具体取决于底层容器的性能特性。

取出(pop

  • 用法:void pop();
  • 描述:移除优先队列中优先级最高的元素。这通常是队列的第一个元素。pop 操作会将最高优先级的元素移除,然后重新排列剩余元素以保持优先队列的性质。
  • 注意:pop 函数不返回被移除的元素。如果你需要访问这个元素,应该先调用 top()
  • 复杂度:同样是对数时间,取决于底层容器。

访问顶部元素(top

  • 用法:const T& top() const;T& top();
  • 描述:返回优先队列中优先级最高的元素的引用。这允许你查看但不移除队列顶部的元素。
  • 复杂度:常数时间。

示例代码

#include <iostream>
#include <queue>
int main() {
    std::priority_queue<int> pq;
    // 插入元素
    pq.push(10);
    pq.push(5);
    pq.push(15);
    // 显示并移除队列顶部元素
    while (!pq.empty()) {
        std::cout << pq.top() << std::endl; // 显示顶部元素
        pq.pop(); // 移除顶部元素
    }
    return 0;
}

这个示例中,优先队列将按照元素的降序排列(默认情况),所以首先输出的是最大的元素。

3. std::priority_queue 的优先级详解

std::priority_queue 中,优先级的判断是基于元素的值和一个比较函数来实现的。默认情况下,比较函数是 std::less<T>,这意味着较大的元素会被视为具有较高的优先级。因此,在默认配置下的 std::priority_queue 实际上是一个最大堆,即队列的顶部始终是当前最大的元素。

如果你想改变优先级的判断方式,比如想要一个最小堆(队列顶部是最小元素),你可以在声明 std::priority_queue 时指定一个不同的比较函数,例如 std::greater<T>

举例说明

  1. 默认情况下(最大堆):
  • 插入元素:10, 5, 15。
  • 由于默认使用 std::less<T>,较大的数字具有更高的优先级。
  • 因此,15 会是队列的顶部元素。
  1. 使用 std::greater<T>(最小堆):
  • 如果声明优先队列时使用 std::greater<T>,则较小的数字将具有更高的优先级。
  • 插入相同的元素(10, 5, 15)后,5 将是队列的顶部元素。

示例代码:使用 std::greater<T>

#include <iostream>
#include <queue>
#include <functional> // 对于 std::greater
int main() {
    // 使用 std::greater 来创建最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
    // 插入元素
    pq.push(10);
    pq.push(5);
    pq.push(15);
    // 显示并移除队列顶部元素
    while (!pq.empty()) {
        std::cout << pq.top() << std::endl; // 显示顶部元素
        pq.pop(); // 移除顶部元素
    }
    return 0;
}

在这个示例中,由于使用了 std::greater<int>,所以最小的元素(5)将会是队列的顶部元素。

4 . std::priority_queue 的优缺点

std::priority_queue 是 C++ 标准库中的一个容器适配器,提供了一组特定的功能,使其适用于特定类型的问题。了解其优点和缺点有助于确定何时使用它。

优点

  1. 高效的元素访问和管理std::priority_queue 提供了对其顶部元素的快速访问(即优先级最高的元素),这在许多算法中非常有用,例如在贪心算法、图算法(如 Dijkstra 算法)中。
  2. 自动元素排序:当元素被加入到队列中时,它们会根据给定的比较函数自动排序。这意味着你总是可以快速访问或删除优先级最高的元素。
  3. 灵活性:通过模板参数,你可以自定义存储的元素类型、底层容器和比较函数,使其适应特定需求。
  4. 易于使用:与标准库中的其他容器一样,std::priority_queue 提供了清晰、一致的 API,使得它易于理解和使用。

缺点

  1. 有限的接口std::priority_queue 只提供了对队列顶部元素的访问。它不支持遍历或直接访问除顶部元素之外的其他元素。
  2. 不支持元素的随机访问:由于其性质,你不能像使用 std::vector 那样随机访问或检索优先队列中的元素。
  3. 不支持修改优先级:一旦元素被加入到 std::priority_queue 中,你就不能更改其优先级或直接更新它。要实现这样的功能,需要从队列中移除该元素,修改后再重新加入。
  4. 内存使用:由于基于底层容器(如 std::vector),std::priority_queue 可能会在内存分配上不如某些专用的堆结构高效。
  5. 不支持迭代器:与大多数其他标准库容器不同,std::priority_queue 不提供迭代器,因此不能用于标准算法库中的函数。

结论

std::priority_queue 非常适合于需要频繁访问和删除优先级最高元素的场景,尤其是在算法中需要这样的操作时。然而,如果你需要更复杂的操作,如元素的随机访问、修改或遍历,那么可能需要考虑其他数据结构。

6. std::priority_queue 适用场景

std::priority_queue 作为一种特殊的队列结构,在 C++ 中主要用于管理一组元素,其中每个元素都有一个优先级。优先队列保证每次取出的元素都是当前优先级最高的。这种特性使得 std::priority_queue 在特定场景下非常有用:

1. 贪心算法

在需要做出局部最优选择的场景中,如在贪心算法中,std::priority_queue 可以用来保持当前可用选项的有序性。例如,在 Huffman 编码和 Dijkstra 的最短路径算法中,优先队列用于选择最小成本或最短路径的节点。

2. 事件驱动的模拟

在事件驱动的模拟(如离散事件模拟)中,事件可以根据它们发生的时间顺序排列在优先队列中。这样可以确保事件按照正确的顺序被处理。

3. 调度算法

在操作系统和任务调度算法中,std::priority_queue 可用于管理不同优先级的任务。例如,处理器时间可以优先分配给优先级最高的任务。

4. 数据流处理

在处理实时数据流,如股票市场数据或社交媒体数据流时,可以用优先队列来跟踪最重要的或最相关的数据项。

5. A* 搜索算法

在路径查找和图搜索算法,特别是 A* 搜索算法中,优先队列用于有效地选择下一个要探索的节点。

6. 优先服务的队列

在需要按优先级处理元素的场景,如客户服务、医疗服务等领域,优先队列可以管理待处理的请求。

7. 堆排序

std::priority_queue 可用于实现堆排序算法,这是一种高效的排序方法,尤其是在处理大数据集时。

注意事项

虽然 std::priority_queue 在这些场景中非常有用,但它也有其限制,如不支持随机访问、不能直接修改元素等。因此,在选择使用它之前,需要考虑这些限制是否会影响到你的应用场景。

7. std::priority_queue 可能的实现

std::priority_queue 在 C++ 中通常是基于堆(heap)数据结构实现的,特别是使用一种称为“二叉堆”的形式。二叉堆是一种完全二叉树,可以有效地支持优先队列的操作。

内部排序算法

  1. 堆排序算法std::priority_queue 使用堆排序算法来维护元素的顺序。在最大堆中,父节点的值总是大于或等于其子节点的值;在最小堆中,则总是小于或等于其子节点的值。
  2. 插入操作push):当新元素被加入时,它首先被放置在堆的末尾(即树的最底层),然后通过一系列的“上浮”操作,将其移动到正确的位置以维护堆的特性。这个过程的时间复杂度是 O(log n)。
  3. 删除操作pop):移除元素(通常是顶部元素)时,堆会用最后一个元素替换顶部元素,然后执行“下沉”操作,将这个元素下移到正确的位置,以保持堆的特性。这个过程的时间复杂度也是 O(log n)。
  4. 查找顶部元素top):查找堆顶元素(优先级最高的元素)是一个常数时间操作,即 O(1)。

我将创建一个Markdown表格,展示C++中std::priority_queue(优先队列)的各种操作的时间复杂度。下面是这个表格:

操作 时间复杂度
插入 O(log n)
移除 O(log n)
查询顶部 O(1)
查询大小 O(1)
检查空 O(1)

解释:

  • 插入:向std::priority_queue中插入一个元素,通常是将其放在底层容器的末尾,然后进行上浮(heapify up)操作。这个操作的时间复杂度为O(log n),其中n是优先队列中的元素数量。
  • 移除:移除顶部元素(最高优先级的元素)涉及到移除堆的根节点,然后进行下沉(heapify down)操作。这个操作同样需要O(log n)的时间。
  • 查询顶部:访问顶部元素(最高优先级的元素)是一个常数时间操作,时间复杂度为O(1),因为它总是位于底层容器的前端。
  • 查询大小:检查std::priority_queue的大小(它包含的元素数量)是一个常数时间操作。
  • 检查空:检查std::priority_queue是否为空也是一个常数时间操作。

请注意,std::priority_queue不支持直接移除或访问顶部元素以外的元素,因此类似随机访问或删除(顶部元素以外)等操作在此不适用。

性能考虑

  • 数据量大时的性能:由于 std::priority_queue 的主要操作(插入和删除)具有 O(log n) 的时间复杂度,因此即使在处理大量数据时,它也能保持良好的性能。这使得它适合用于需要频繁插入和删除元素的场景。
  • 内存使用std::priority_queue 的内存使用取决于其底层容器(默认是 std::vector)。由于是基于数组的实现,它通常比基于节点的数据结构(如链表)更加内存高效。
  • 元素比较:元素的比较次数取决于堆的高度,即 O(log n)。你可以通过提供自定义的比较函数来影响排序行为。这对于处理复杂对象或自定义排序准则特别重要。

总体来说,std::priority_queue 在处理具有动态优先级的数据集合方面非常有效,特别是在需要快速访问、添加或移除优先级最高或最低元素的应用中。然而,它不适用于需要频繁访问或修改队列中间元素的场景。

以下是std::priority_queue数据结构的一个简化的C++实现。这个实现使用了最大堆来存储元素,其中堆的顶部元素(位于数组的第一个位置)是最大的。

#include <vector>
#include <iostream>
template<typename T>
class PriorityQueue {
private:
    std::vector<T> heap;
    void heapifyUp(int index) {
        while (index > 0 && heap[(index - 1) / 2] < heap[index]) {
            std::swap(heap[index], heap[(index - 1) / 2]);
            index = (index - 1) / 2;
        }
    }
    void heapifyDown(int index) {
        int size = heap.size();
        int largest = index;
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        if (left < size && heap[left] > heap[largest]) {
            largest = left;
        }
        if (right < size && heap[right] > heap[largest]) {
            largest = right;
        }
        if (largest != index) {
            std::swap(heap[index], heap[largest]);
            heapifyDown(largest);
        }
    }
public:
    bool isEmpty() const {
        return heap.empty();
    }
    T top() const {
        if (!isEmpty()) {
            return heap.front();
        }
        throw std::out_of_range("PriorityQueue is empty");
    }
    void push(const T& value) {
        heap.push_back(value);
        int index = heap.size() - 1;
        heapifyUp(index);
    }
    void pop() {
        if (isEmpty()) {
            throw std::out_of_range("PriorityQueue is empty");
        }
        heap[0] = heap.back();
        heap.pop_back();
        heapifyDown(0);
    }
};

在这个实现中,我们有:

  • heapifyUp 函数,用于在插入元素时调整堆。
  • heapifyDown 函数,用于在删除顶部元素后调整堆。
  • push 函数,用于添加元素到优先队列。
  • pop 函数,用于移除优先级最高的元素。
  • top 函数,用于获取优先级最高的元素但不移除它。
  • isEmpty 函数,用于检查优先队列是否为空。

请注意,这是一个简化的实现,专门用于教学目的。标准库中的std::priority_queue提供了更复杂的功能和更优的性能。此外,异常处理和边界条件检查在实际应用中应该更加全面。

结语

在我们的编程学习之旅中,理解是我们迈向更高层次的重要一步。然而,掌握新技能、新理念,始终需要时间和坚持。从心理学的角度看,学习往往伴随着不断的试错和调整,这就像是我们的大脑在逐渐优化其解决问题的“算法”。

这就是为什么当我们遇到错误,我们应该将其视为学习和进步的机会,而不仅仅是困扰。通过理解和解决这些问题,我们不仅可以修复当前的代码,更可以提升我们的编程能力,防止在未来的项目中犯相同的错误。

我鼓励大家积极参与进来,不断提升自己的编程技术。无论你是初学者还是有经验的开发者,我希望我的博客能对你的学习之路有所帮助。如果你觉得这篇文章有用,不妨点击收藏,或者留下你的评论分享你的见解和经验,也欢迎你对我博客的内容提出建议和问题。每一次的点赞、评论、分享和关注都是对我的最大支持,也是对我持续分享和创作的动力。

目录
相关文章
|
2月前
|
存储 算法
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
这篇文章详细介绍了图的概念、表示方式以及深度优先遍历和广度优先遍历的算法实现。
61 1
数据结构与算法学习二二:图的学习、图的概念、图的深度和广度优先遍历
|
2月前
|
算法 Java 数据库
数据结构与算法学习十五:哈希表
这篇文章详细介绍了哈希表的概念、应用实例、实现思路,并提供了使用Java实现的哈希表代码。
55 0
数据结构与算法学习十五:哈希表
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习之顺序表【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找等具体详解步骤以及举例说明
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第3章之IKUN和I原达人之数据结构与算法系列学习栈与队列精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
1月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
1月前
|
存储 算法 安全
2024重生之回溯数据结构与算法系列学习【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构的基本概念;算法的基本概念、特性以及时间复杂度、空间复杂度等举例说明;【含常见的报错问题及其对应的解决方法】