当前位置：首页 > article >正文

深入探讨优先队列：原理、实现与应用

article 2025/2/22 12:53:38

一、优先队列（Priority Queue）概述

二、优先队列的核心操作

三、优先队列的实现方式

四、C++中的优先队列

1、std::priority_queue的基本用法

2、自定义比较函数

3、自定义数据结构

五、优先队列的时间复杂度

六、优先队列的应用场景

总结

一、优先队列（Priority Queue）概述

优先队列是一种抽象数据类型，它允许在队列中的元素具有优先级。与普通队列（FIFO）不同，优先队列中的元素按照优先级顺序出队，而不是按照插入顺序。优先队列通常用于需要动态管理元素优先级的场景，如任务调度、图算法（如Dijkstra算法）、Huffman编码等。

二、优先队列的核心操作

插入（Insert/Push）：将一个元素插入到优先队列中。
删除最大/最小元素（DeleteMax/DeleteMin/Pop）：移除并返回优先队列中优先级最高或最低的元素。
查看最大/最小元素（Peek/Top）：返回优先队列中优先级最高或最低的元素，但不移除它。
判断队列是否为空（IsEmpty）：检查优先队列是否为空。
获取队列大小（Size）：返回优先队列中元素的数量。

三、优先队列的实现方式

优先队列可以通过多种数据结构实现，常见的有：

数组或链表：简单但效率较低，插入和删除操作的时间复杂度为O(n)。
二叉堆（Binary Heap）：最常用的实现方式，插入和删除操作的时间复杂度为O(log n)。
斐波那契堆（Fibonacci Heap）：在某些操作（如合并）上具有更好的时间复杂度，但实现复杂。
平衡二叉搜索树（如AVL树、红黑树）：插入和删除操作的时间复杂度为O(log n)，但实现较为复杂。

四、C++中的优先队列

C++标准库（STL）提供了std::priority_queue容器适配器，它通常基于二叉堆实现。std::priority_queue是一个模板类，定义在<queue>头文件中。

`1、std::priority_queue`的基本用法

#include <iostream>
#include <queue>

int main() {
    // 默认情况下，std::priority_queue 是一个最大堆
    std::priority_queue<int> maxHeap;

    // 插入元素
    maxHeap.push(10);
    maxHeap.push(30);
    maxHeap.push(20);

    // 查看最大元素
    std::cout << "Top element: " << maxHeap.top() << std::endl; // 输出 30

    // 删除最大元素
    maxHeap.pop();
    std::cout << "Top element after pop: " << maxHeap.top() << std::endl; // 输出 20

    // 判断队列是否为空
    if (!maxHeap.empty()) {
        std::cout << "Priority queue is not empty." << std::endl;
    }

    // 获取队列大小
    std::cout << "Size of priority queue: " << maxHeap.size() << std::endl;

    return 0;
}

2、自定义比较函数

std::priority_queue默认是一个最大堆，即优先级最高的元素（最大值）位于堆顶。如果需要实现最小堆，可以通过自定义比较函数来实现。

#include <iostream>
#include <queue>
#include <vector>
#include <functional> // 用于 std::greater

int main() {
    // 使用 std::greater<int> 作为比较函数，实现最小堆
    std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;

    // 插入元素
    minHeap.push(10);
    minHeap.push(30);
    minHeap.push(20);

    // 查看最小元素
    std::cout << "Top element: " << minHeap.top() << std::endl; // 输出 10

    // 删除最小元素
    minHeap.pop();
    std::cout << "Top element after pop: " << minHeap.top() << std::endl; // 输出 20

    return 0;
}

3、自定义数据结构

std::priority_queue也可以用于自定义数据结构。需要为自定义数据结构提供比较函数或重载比较运算符。

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

struct Task {
    int priority;
    std::string name;

    // 重载小于运算符，用于最大堆
    bool operator<(const Task& other) const {
        return priority < other.priority;
    }

    // 重载大于运算符，用于最小堆
    bool operator>(const Task& other) const {
        return priority > other.priority;
    }
};

int main() {
    // 最大堆，根据 Task 的 priority 排序
    std::priority_queue<Task> maxHeap;

    maxHeap.push({10, "Task A"});
    maxHeap.push({30, "Task B"});
    maxHeap.push({20, "Task C"});

    std::cout << "Top task: " << maxHeap.top().name << " (Priority: " << maxHeap.top().priority << ")" << std::endl;

    // 最小堆，根据 Task 的 priority 排序
    std::priority_queue<Task, std::vector<Task>, std::greater<Task>> minHeap;

    minHeap.push({10, "Task A"});
    minHeap.push({30, "Task B"});
    minHeap.push({20, "Task C"});

    std::cout << "Top task: " << minHeap.top().name << " (Priority: " << minHeap.top().priority << ")" << std::endl;

    return 0;
}