[C++]优先队列

C++ 中的 优先队列（priority_queue）是一个容器适配器，用来管理带优先级的队列，内部采用堆（通常是二叉堆）来维护元素的顺序。优先队列保证每次取出的元素是队列中优先级最高的元素。

1. 基本概念

优先队列是一种特殊的队列，元素之间有优先级关系。默认情况下，优先队列中的元素是大顶堆，即每次出队的元素是优先级最高（值最大）的元素。

2. 常用操作

C++ 提供了标准库中的 priority_queue 类，常见的操作如下：

push(): 将元素插入队列。
pop(): 移除队列中优先级最高的元素。
top(): 返回队列中优先级最高的元素，但不移除。
empty(): 判断队列是否为空。
size(): 返回队列中元素的数量。

#include <iostream>
#include <queue>

int main() {
    std::priority_queue<int> pq;
    pq.push(10);
    pq.push(30);
    pq.push(20);
    
    std::cout << "Top element: " << pq.top() << std::endl;  // 输出 30
    pq.pop();
    std::cout << "Top element after pop: " << pq.top() << std::endl;  // 输出 20
}

3. 自定义比较函数

默认情况下，priority_queue 是一个大顶堆，即最大的元素优先出队。如果需要自定义优先级（例如实现小顶堆或自定义比较逻辑），可以通过传递比较函数或者仿函数来实现。

小顶堆实现（使用内置比较器 std::greater<T>）：

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

int main() {
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq;
    pq.push(10);
    pq.push(30);
    pq.push(20);
    
    std::cout << "Top element: " << pq.top() << std::endl;  // 输出 10
}

自定义结构体的比较：

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

struct Task {
    int priority;
    std::string name;
    
    // 自定义比较函数
    bool operator<(const Task& other) const {
        return priority < other.priority;  // 优先级低的任务放在前面
    }
};

int main() {
    std::priority_queue<Task> pq;
    pq.push({1, "Task1"});
    pq.push({3, "Task3"});
    pq.push({2, "Task2"});
    
    std::cout << "Top task: " << pq.top().name << std::endl;  // 输出 Task3
}

仿函数

在 C++ 中，除了可以使用内置的比较函数（如 std::greater<T>），还可以通过自定义的仿函数来实现优先队列的自定义比较逻辑。

什么是仿函数？

仿函数（Functor）是指像函数一样使用的对象。它是通过在类中重载 operator() 运算符实现的。当一个对象实现了这个运算符，它就可以像函数一样被调用。仿函数的优势在于它可以保存状态，并且可以在优先队列等数据结构中提供灵活的自定义比较逻辑。

使用仿函数实现自定义比较逻辑

在优先队列中，我们可以通过仿函数来自定义优先级的比较规则，例如可以根据某个属性排序，或者复杂的多层次比较。

示例：自定义仿函数排序

假设我们有一个任务结构体 Task，其中有 priority 和 name 两个成员。我们希望根据 priority 来定义优先队列的顺序，但我们想要用仿函数而不是结构体中的 < 运算符来进行比较。

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

// 任务结构体
struct Task {
    int priority;
    std::string name;
};

// 自定义仿函数，用于比较 Task 的优先级
struct TaskCompare {
    bool operator()(const Task& t1, const Task& t2) const {
        return t1.priority < t2.priority;  // 优先级低的任务排在队列后面
    }
};

int main() {
    // 使用仿函数 TaskCompare 作为优先队列的比较函数
    std::priority_queue<Task, std::vector<Task>, TaskCompare> pq;

    pq.push({1, "Task1"});
    pq.push({3, "Task3"});
    pq.push({2, "Task2"});

    while (!pq.empty()) {
        std::cout << "Top task: " << pq.top().name << " with priority " << pq.top().priority << std::endl;
        pq.pop();
    }
    
    return 0;
}

仿函数与函数指针的区别

仿函数与传统的函数指针相比有如下优点：

状态保持：仿函数可以携带状态（通过成员变量），而函数指针只能调用不带状态的函数。
内联优化：编译器通常能够将仿函数内联，从而提高运行时效率，而函数指针的调用需要通过指针间接调用，效率较低。

示例：带状态的仿函数

我们可以通过仿函数保存一些额外的状态信息。例如，假设我们想要自定义优先队列的顺序，同时根据一个给定的阈值来动态决定任务的优先级比较。

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

// 任务结构体
struct Task {
    int priority;
    std::string name;
};

// 带状态的仿函数
struct DynamicTaskCompare {
    int threshold;  // 比较任务优先级的阈值
    
    DynamicTaskCompare(int t) : threshold(t) {}

    bool operator()(const Task& t1, const Task& t2) const {
        if (t1.priority >= threshold && t2.priority < threshold) {
            return false;  // t1 优先
        }
        if (t1.priority < threshold && t2.priority >= threshold) {
            return true;  // t2 优先
        }
        return t1.priority < t2.priority;  // 优先级大的任务排在前面
    }
};

int main() {
    // 使用带状态的仿函数进行优先级比较
    std::priority_queue<Task, std::vector<Task>, DynamicTaskCompare> pq(DynamicTaskCompare(2));
    
    pq.push({1, "Task1"});
    pq.push({3, "Task3"});
    pq.push({2, "Task2"});

    while (!pq.empty()) {
        std::cout << "Top task: " << pq.top().name << " with priority " << pq.top().priority << std::endl;
        pq.pop();
    }
    
    return 0;
}

在这个示例中，DynamicTaskCompare 仿函数通过 threshold 这个状态来动态决定任务的优先级。这个特性在某些动态排序场景下非常有用。

仿函数与 Lambda 表达式

C++11 引入了 Lambda 表达式，它可以提供类似仿函数的功能，并且代码更加简洁。如果比较逻辑非常简单，可以使用 Lambda 表达式代替仿函数。例如：

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

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

int main() {
    auto compare = [](const Task& t1, const Task& t2) {
        return t1.priority < t2.priority;  // 优先级低的任务排在队列后面
    };

    std::priority_queue<Task, std::vector<Task>, decltype(compare)> pq(compare);

    pq.push({1, "Task1"});
    pq.push({3, "Task3"});
    pq.push({2, "Task2"});

    while (!pq.empty()) {
        std::cout << "Top task: " << pq.top().name << " with priority " << pq.top().priority << std::endl;
        pq.pop();
    }
    
    return 0;
}

4. 底层实现

priority_queue 的底层实现通常依赖于堆，具体来说是 二叉堆。C++ 标准库使用 std::vector 作为底层存储容器来保存元素，并通过堆的操作来保持优先队列的性质。

堆操作：
- 插入元素时，会调用堆的 上浮操作，确保新元素插入后堆的结构保持完整。
- 删除最大（或最小）元素时，会调用 下沉操作，将堆顶元素与子节点交换，确保堆的有序性。

C++ 标准库提供了用于堆操作的算法：

std::make_heap: 将范围内的元素构造成堆。

功能：将一个无序的范围转换为一个堆。默认情况下，它创建一个 最大堆（即堆顶是最大值），但也可以通过传递自定义比较器创建最小堆或其他类型的堆。

语法：

1	`void make_heap(RandomIt first, RandomIt last);`

参数：

first 和 last 指向范围的起始和结束，表示要构建堆的范围。

示例：

#include <iostream>
#include <algorithm>
#include <vector>

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5};
    
    // 构建一个最大堆
    std::make_heap(v.begin(), v.end());
    
    std::cout << "Max heap: ";
    for (int i : v) {
        std::cout << i << " ";  // 输出: 9 6 5 5 1 4 2 1 3
    }
    std::cout << std::endl;

    return 0;
}

std::push_heap: 向堆中插入元素。

功能：在一个堆中插入新元素（即将新元素添加到容器末尾后，通过 push_heap 调整容器使其重新成为合法的堆结构）。使用时，必须先把新元素手动插入到容器末尾，再调用 push_heap。

语法：

1	`void push_heap(RandomIt first, RandomIt last);`

参数：

first 和 last 指向堆的起始和结束，其中 last 为新插入的元素的下一个位置。

示例：

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5};
    std::make_heap(v.begin(), v.end());
    
    // 移除堆顶元素
    std::pop_heap(v.begin(), v.end());  // 9 被移动到末尾
    v.pop_back();  // 实际移除该元素

    std::cout << "Heap after pop: ";
    for (int i : v) {
        std::cout << i << " ";  // 输出: 6 5 5 3 1 4 2 1
    }
    std::cout << std::endl;

    return 0;
}

std::pop_heap: 从堆中删除元素。

功能：将堆顶元素移到容器的末尾，同时保持其他元素的堆结构（即重新调整剩余元素成为一个合法的堆）。注意，pop_heap 只是将堆顶元素移到末尾，不会从容器中移除它，必须手动使用 container.pop_back()。

语法：

1	`void pop_heap(RandomIt first, RandomIt last);`

参数：

first 和 last 指向堆的起始和结束，last 指向的元素将是新堆顶元素后的第一个非堆元素（即末尾元素）。

示例：

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5};
    std::make_heap(v.begin(), v.end());
    
    // 移除堆顶元素
    std::pop_heap(v.begin(), v.end());  // 9 被移动到末尾
    v.pop_back();  // 实际移除该元素

    std::cout << "Heap after pop: ";
    for (int i : v) {
        std::cout << i << " ";  // 输出: 6 5 5 3 1 4 2 1
    }
    std::cout << std::endl;

    return 0;
}

std::sort_heap: 对堆中的元素进行排序。

功能：对一个堆进行排序。注意，调用 sort_heap 后，堆结构将被破坏，但数组会按升序排序（默认情况下）。这就是堆排序的关键步骤。

语法：

1	`void sort_heap(RandomIt first, RandomIt last);`

参数：

first 和 last 指向堆的起始和结束。

示例：

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5};
    std::make_heap(v.begin(), v.end());
    
    // 对堆进行排序
    std::sort_heap(v.begin(), v.end());

    std::cout << "Sorted heap: ";
    for (int i : v) {
        std::cout << i << " ";  // 输出: 1 1 2 3 4 5 5 6 9
    }
    std::cout << std::endl;

    return 0;
}

5. 性能分析

priority_queue 的时间复杂度与其底层堆实现直接相关。由于使用堆结构，以下是常见操作的时间复杂度：

插入元素（push）: O(log n)，因为需要进行上浮操作。
取最大/最小元素（top）: O(1)，只需返回堆顶元素。
删除最大/最小元素（pop）: O(log n)，因为需要进行下沉操作。

由于 priority_queue 是基于二叉堆的实现，因此它具有较高的效率，适合用于需要频繁插入和删除最大（最小）元素的场景。

在分析 C++ 中与堆操作相关的 make_heap、pop_heap、push_heap 和 sort_heap 函数的性能时，主要考虑堆的性质和这些操作的时间复杂度。堆是一棵完全二叉树，通常使用数组来实现，堆的高度是 O(log n)，其中 n 是堆中元素的个数。

make_heap 的性能分析

功能：make_heap 函数将一个无序的序列转化为一个合法的堆。
时间复杂度：O(n)。

虽然每次插入一个元素到堆的复杂度为 O(log n)，看似将 n 个元素插入到堆中会导致 O(n log n) 的时间复杂度。然而，make_heap 使用了一种自底向上的建堆方法，其时间复杂度为 O(n)。

分析：

自顶向下插入的复杂度为 O(n log n)，但 make_heap 采用的是自底向上的建堆方法，它从堆的最后一个非叶子节点开始，逐步调整子堆的顺序，最终构建出一个完整的堆。
每个节点的调整最多移动 log n 步，但较低层的节点数量多，且调整所需的移动步数较少，因此整体复杂度是线性的，即 O(n)。

pop_heap 的性能分析

功能：pop_heap 将堆顶元素（最大或最小值）移动到序列的末尾，同时保持剩余序列的堆结构。
时间复杂度：O(log n)。

分析：

pop_heap 先将堆顶元素与最后一个元素交换，然后对交换后的堆（除去最后一个元素）进行下沉操作（即调整堆），从根节点开始逐层向下调整，以保持堆的性质。
下沉操作的最坏情况下需要进行 log n 次比较和交换操作，因此时间复杂度为 O(log n)。

push_heap 的性能分析

功能：push_heap 在序列的末尾插入一个新元素，并调整序列使其仍然满足堆的性质。
时间复杂度：O(log n)。

分析：

当将一个新元素添加到堆中时，它首先被插入到堆的末尾。然后通过上浮操作，将该元素向上移动，直到满足堆的性质。
上浮操作在最坏情况下可能需要从堆的底部移动到根节点，这需要最多 log n 步操作，因此时间复杂度为 O(log n)。

sort_heap 的性能分析

功能：sort_heap 将堆排序为一个有序数组。它通过依次调用 pop_heap，将堆顶元素移到序列末尾，并调整剩余序列为一个合法的堆，最终完成排序。
时间复杂度：O(n log n)。

分析：

堆排序是通过重复调用 pop_heap 实现的，pop_heap 每次将堆顶元素移动到末尾，然后调整剩余的堆，复杂度为 O(log n)。
因为 sort_heap 需要对 n 个元素依次调用 pop_heap，因此总的时间复杂度为 O(n log n)。

6. 使用场景

优先队列广泛用于以下场景：

任务调度：根据优先级安排任务执行顺序。
图算法：如 Dijkstra 最短路径算法、A* 搜索算法等。
事件驱动模拟：处理时间敏感的事件。
动态排序问题：实时获取最大或最小元素的情况。

编程语言

#C++ #数据结构

[C++]优先队列

https://erlsrnby04.github.io/2024/10/05/C-优先队列/

作者

ErlsrnBy04

发布于

2024年10月5日

许可协议

[C++]类型极端值上一篇

[LC]23.合并k个升序链表下一篇