In-depth explanation of C++ priority_queue.

2 years ago
Liam
3 minutes

priority_queue is a container in the C++ STL that organizes elements in a queue based on priority. The element with the highest priority (according to the comparison function) is always positioned at the front of the queue.

Features of a priority queue:

  1. The order of elements is determined by the comparison function, by default, the elements are arranged in the form of a max heap, meaning the value of the root node is the largest.
  2. When extracting elements from a priority_queue, the element with the highest priority is always extracted.
  3. Priority queues are typically implemented using binary heaps.

Steps for using priority_queue:

  1. Can you please explain it again in a simpler way?
  2. Declare a priority_queue object, specifying the element type and comparison function, where the comparison function can be a function pointer, function object, or lambda expression.
  3. Inserting elements into a priority_queue: push() function.
  4. Retrieve elements from the priority_queue: using the top() function.
  5. Remove elements from the priority queue using the pop() function.
  6. Check if the priority_queue is empty using the empty() function.
  7. Use the function size() to obtain the number of elements in a priority_queue.

Common functions of a priority_queue:

  1. Insert element into the priority queue using the function push(element).
  2. top(): returns the element with the highest priority in the priority queue.
  3. Remove the element with the highest priority from the priority_queue using pop().
  4. empty(): used to check if the priority_queue is empty.
  5. size(): returns the number of elements in the priority_queue.

Sample code:

#include <iostream>
#include <queue>

int main() {
    // 声明一个存放整数的priority_queue，默认为大根堆
    std::priority_queue<int> pq;

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

    // 获取优先级最高的元素
    std::cout << "Top element: " << pq.top() << std::endl;

    // 删除优先级最高的元素
    pq.pop();

    // 判断priority_queue是否为空
    if (pq.empty()) {
        std::cout << "Priority queue is empty." << std::endl;
    } else {
        std::cout << "Priority queue is not empty." << std::endl;
    }

    // 获取priority_queue中元素的个数
    std::cout << "Size of priority queue: " << pq.size() << std::endl;

    return 0;
}

Output results:

Top element: 30
Priority queue is not empty.
Size of priority queue: 2

This is a simple example of a priority_queue, demonstrating basic operations such as inserting elements, getting the highest priority element, deleting the highest priority element, checking if it is empty, and getting the number of elements. In actual use, custom comparison functions can be implemented to achieve different priority orders according to needs.

bannerAds