C++之优先队列(priority_queue)

发布时间:2024年01月08日

priority_queue 是 C++ 标准模板库(STL)中的一种容器适配器,它提供了一个基于优先级的队列。这意味着它存储的元素是按照一定的优先级进行排序的,每次访问队头元素都是当前队列中优先级最高的元素。

在 C++ 中,priority_queue 通常使用堆(heap)来实现,堆是一种特殊的二叉树结构,满足堆的性质。C++ 中的 priority_queue 默认使用大顶堆,也就是队头元素是最大的元素。你可以通过提供比较函数来使用小顶堆。

以下是一个简单的示例,演示了如何使用 priority_queue:


#include <iostream>
#include <queue>

int main() {
    // 创建一个大顶堆的 priority_queue
    std::priority_queue<int> maxHeap;

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

    // 访问队头元素
    std::cout << "Top element: " << maxHeap.top() << std::endl;

    // 弹出队头元素
    maxHeap.pop();

    // 访问新的队头元素
    std::cout << "Top element after pop: " << maxHeap.top() << std::endl;

    return 0;
}

在这个示例中,std::priority_queue 被创建为大顶堆,默认情况下,元素的比较使用 < 操作符。你可以通过提供自定义的比较函数来创建小顶堆。

例如,如果要创建一个小顶堆,可以这样做:


#include <iostream>
#include <queue>

// 自定义比较函数,使得小的元素优先级高
struct Compare {
    bool operator()(int a, int b) {
        return a > b;
    }
};

int main() {
    // 创建一个小顶堆的 priority_queue
    std::priority_queue<int, std::vector<int>, Compare> minHeap;

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

    // 访问队头元素
    std::cout << "Top element: " << minHeap.top() << std::endl;

    // 弹出队头元素
    minHeap.pop();

    // 访问新的队头元素
    std::cout << "Top element after pop: " << minHeap.top() << std::endl;

    return 0;
}

这个例子中,Compare 结构体定义了自定义的比较函数,确保小的元素优先级更高。

组合实例:

#include <iostream>
#include <queue>

// 自定义比较函数,使得小的元素优先级高
struct Compare {
    bool operator()(int a, int b) {
        return a > b;
    }
};

int main() {
    // 创建一个大顶堆的 priority_queue
    std::priority_queue<int> maxHeap;

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

    // 访问队头元素
    std::cout << "Top Max element: " << maxHeap.top() << std::endl;

    // 弹出队头元素
    maxHeap.pop();

    // 访问新的队头元素
    std::cout << "Top Max element after pop: " << maxHeap.top() << std::endl;


    // 创建一个小顶堆的 priority_queue
    std::priority_queue<int, std::vector<int>, Compare> minHeap;

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

    // 访问队头元素
    std::cout << "Top Min element: " << minHeap.top() << std::endl;

    // 弹出队头元素
    minHeap.pop();

    // 访问新的队头元素
    std::cout << "Top  Min element after pop: " << minHeap.top() << std::endl;

    return 0;
}

文章来源:https://blog.csdn.net/qq_42244167/article/details/135461605
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。