C++ container classes<priority_queue>

In C++,<priority_queue>Is part of the Standard Template Library (STL) and is used to implement priority queues.

A priority queue is a special type of queue that allows us to quickly access the element with the highest (or lowest) priority in the queue.

In C++,priority_queueBy default, it is a max-heap, which means the top element of the queue always has the largest value.

priority_queueIs a container adapter that provides heap operations on the underlying container. It does not provide iterators and does not support random access.

Syntax

The following arepriority_queueBasic syntax:

#include <queue>

// 声明一个整型优先队列
priority_queue<int> pq;

// 声明一个自定义类型的优先队列，需要提供比较函数
struct compare {
    bool operator()(int a, int b) {
        return a > b; // 这里定义了最小堆
    }
};
priority_queue<int, vector<int>, compare> pq_min;

Common operations

  • empty(): Check whether the queue is empty.
  • size(): Return the number of elements in the queue.
  • top(): Return the element at the top of the queue (without removing it).
  • push(): Add an element to the queue.
  • pop(): Remove the element at the top of the queue.

Example

Below is an example usingpriority_queueA simple example of it: we will create a max-heap and show how to add elements and retrieve the element at the top of the queue.

Example

#include <iostream>
#include <queue>

int main() {
    // Create an integer priority queue
    std::priority_queue<int> pq;

    // Add elements to the priority queue
    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);

    // Output the elements in the queue
    std::cout << "Elements in the queue:" << std::endl;
    while (!pq.empty()) {
        std::cout << pq.top() << std::endl;
        pq.pop();
    }

    return 0;
}

Output result:

队列中的元素：
50
30
20
10

Custom priority

If you need a min-heap, you can implement it by customizing the comparison function:

Example

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

struct compare {
    bool operator()(int a, int b) {
        return a > b; // Define a min-heap
    }
};

int main() {
    // Create a custom-type priority queue using a min-heap
    std::priority_queue<int, std::vector<int>, compare> pq_min;

    // Add elements to the priority queue
    pq_min.push(30);
    pq_min.push(10);
    pq_min.push(50);
    pq_min.push(20);

    // Output the elements in the queue
    std::cout << "Elements in the min-heap:" << std::endl;
    while (!pq_min.empty()) {
        std::cout << pq_min.top() << std::endl;
        pq_min.pop();
    }

    return 0;
}

Output result:

最小堆中的元素：
10
20
30
50

<priority_queue>It is a very useful container in the C++ STL, especially suitable for scenarios where fast access to the highest or lowest priority element is needed. By customizing the comparison function, we can easily implement a max-heap or a min-heap. I hope this article can help beginners better understand and use it.priority_queue。

other extensions