Back to all concepts
Intermediate 11 min

Priority Queue

Master std::priority_queue for automatically maintaining elements in priority order with O(log n) operations

Learn priority_queue for efficient priority-based processing where the highest priority element is always accessible in O(1).

A Simple Example 

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

int main() {
    // Max-heap by default (largest value has highest priority)
    std::priority_queue<int> pq;

    pq.push(30);
    pq.push(10);
    pq.push(50);
    pq.push(20);

    std::cout << "Priority queue (max-heap):" << "\n";
    while (!pq.empty()) {
        std::cout << pq.top() << " ";  // Always gets largest
        pq.pop();
    }
    std::cout << "\n";  // Output: 50 30 20 10

    // Min-heap (smallest value has highest priority)
    std::priority_queue<int, std::vector<int>, std::greater<int>> minPQ;

    minPQ.push(30);
    minPQ.push(10);
    minPQ.push(50);
    minPQ.push(20);

    std::cout << "Priority queue (min-heap):" << "\n";
    while (!minPQ.empty()) {
        std::cout << minPQ.top() << " ";  // Always gets smallest
        minPQ.pop();
    }
    std::cout << "\n";  // Output: 10 20 30 50

    return 0;
}

Breaking It Down

Priority Queue Basics

  • What it is: Heap-based container adapter that maintains partial ordering
  • Always provides access to highest-priority element in O(1)
  • Insert and remove are O(log n)
  • Use for: Task scheduling, event processing, graph algorithms

Max-Heap vs Min-Heap

  • Max-heap (default): Largest value has highest priority
  • Min-heap: Smallest value has highest priority (use std::greater<T>)
  • Both maintain heap property efficiently
  • Remember: Choose based on whether you want max or min element first

Heap Property - Partial Ordering

  • What it is: Parent is always greater (or less) than children
  • NOT fully sorted - only the top element is guaranteed to be max/min
  • This partial ordering allows O(log n) operations
  • Remember: More efficient than keeping fully sorted

Operations and Complexity

  • top(): O(1) - access highest priority element
  • push(): O(log n) - insert and bubble up
  • pop(): O(log n) - remove top and reorganize
  • Remember: Cannot iterate or access non-top elements

Why This Matters

  • Priority queues are essential for algorithms that need to process items in order of importance, not arrival time.
  • They power Dijkstra's shortest path algorithm, task schedulers, event-driven simulations, and many optimization problems.
  • Understanding priority queues opens the door to efficient solutions for complex problems.

Critical Insight

Priority queue isn't sorting elements - it's maintaining a heap property where the parent is always greater (or less) than its children. This partial ordering is much faster than full sorting!

When you pop an element, it reorganizes in O(log n) to maintain the heap property.

Think of it as a tournament bracket where the winner is always known, but when the winner leaves, you only need one quick match to find the new winner!

Best Practices

Choose max-heap vs min-heap based on needs: Default is max-heap. Use std::greater for min-heap.

Reserve underlying vector if size known: Can improve performance by avoiding reallocations.

Use for priority-based processing: When order of importance matters more than arrival order.

Remember it's not sorted: Only the top element is guaranteed to be in position.

Common Mistakes

Wrong comparison operator: For max-heap, a < b means a has LOWER priority than b. It can be confusing.

Trying to access non-top elements: Priority queue only exposes top(). Cannot iterate or access other elements.

Expecting full sorting: Only the top element is guaranteed to be max/min. The rest maintain heap property, not full order.

Debug Challenge

This task scheduler needs to process highest priority tasks first. Click the highlighted line to fix it:

1 #include <iostream>
2 #include <queue>
3
4 int main() {
5 std::queue<int> tasks;
6 tasks.push(5); // Priority 5
7 tasks.push(1); // Priority 1
8 tasks.push(10); // Priority 10 (highest)
9 // Should process priority 10 first
10 return 0;
11 }

Quick Quiz

  1. What's the time complexity of priority_queue::push()?
O(log n)
O(1)
O(n)
  1. How do you create a min-heap priority queue?
std::priority_queue<int, std::vector<int>, std::greater<int>>
std::priority_queue<int>::min_heap
Just use operator> instead of operator<

Practice Playground

Time to try out what you just learned! Play with the example code below, experiment by making changes and running the code to deepen your understanding.

Lesson Progress

  • Fix This Code
  • Quick Quiz
  • Practice Playground - run once