Topic 59 of 91 9. C++ Standard Template Library (STL) Interactive Tutorial

std::priority_queue in C++: Priority-Based Element Processing

7 mins read Last updated: 26 Sep 2026 16,083 views

On This Page0 sectionsQuick jump to subtopic

Direct Answer & Core Concept

std::priority_queue is a container adapter that provides constant time lookup ($O(1)$) of the highest (or lowest) priority element using a binary heap (usually backed by std::vector via std::make_heap/push_heap/pop_heap). By default, it is a Max-Heap using std::less; a Min-Heap is created using std::greater.

Detailed Explanation & Mechanics

1. Max-Heap vs Min-Heap Declaration:

Max-Heap (Default): std::priority_queue
Min-Heap: std::priority_queue, std::greater>

main.cpp

Run Online

BINARY MAX-HEAP CONCEPT:
             [95 (top)]
             /        \
           [70]       [80]
           /  \       /
         [30] [50]  [60]

2. Time Complexities:

top(): $O(1)$
push(): $O(\log N)$
pop(): $O(\log N)$

Runnable Code Example: std::priority_queue in C++: Priority-Bas

C++20 / C++23

main.cpp

Run Online

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

struct Patient {
    std::string name;
    int triagePriority; // Higher number = higher medical urgency

    bool operator<(const Patient& other) const {
        return triagePriority < other.triagePriority; // Defines Max-Heap
    }
};

int main() {
    std::priority_queue<Patient> erQueue;

    erQueue.push({"John (Sprained Ankle)", 2});
    erQueue.push({"Sarah (Cardiac Arrest)", 10});
    erQueue.push({"Mike (Fever)", 4});

    std::cout << "Emergency Room Patient Processing Order:\n";
    while (!erQueue.empty()) {
        const auto& p = erQueue.top();
        std::cout << "  - Treating: " << p.name << " [Priority: " << p.triagePriority << "]\n";
        erQueue.pop();
    }
    return 0;
}

Common C++ Technical Interview Questions & Answers

Interview Prep

Q: What algorithms power `std::priority_queue` internally?

A: It uses binary heap algorithms from ``: `std::push_heap`, `std::pop_heap`, and `std::make_heap` on an underlying `std::vector`.

Q: How do you create a Min-Heap priority queue of integers in C++?

A: `std::priority_queue, std::greater> minHeap;`

Key Takeaways, Modern Best Practices & Idioms

C++ Best Practices & Production Rules

• Use std::priority_queue for Dijkstra's shortest path algorithm, A* pathfinding, and event-driven simulations.
• Remember that top() returns a const reference; modify items only by popping and re-inserting.
• Always verify !pq.empty() before accessing .top() or calling .pop().

Previous Topicstd::deque in C++: Efficient Insertion From Both Ends

Next Topicstd::stack in C++: LIFO Operations and Stack Management