Home | Projects | Notes > C++ Programming > Container Adaptor - std::priority_queue

Container Adaptor - std::priority_queue

std::priority_queue

• Declared in the <queue> header file.

• priority_queue is a container adaptor, just like stack and queue.

• It allows insertion and removal of elements based on priority, always from the front of the container.

• Elements are inserted according to priority — by default, the largest value is always at the front.

  • When accessing the front element, it is guaranteed to be the largest in the container.

• Internally, elements are stored in a vector by default, but a heap data structure is used behind the scenes.

  • (Note: A heap data structure is different from heap memory — don’t confuse the two.)

• Iterators are not supported because they don’t align with how a priority queue manages element order.

• Use cases:

  • OS priority-based task scheduling and process management

  • Event-driven simulations (e.g., network simulators, hardware simulators, CPU cycle modeling)

  • Huffman Coding (data compression algorithms; ZIP, JPEG, MP3)

  • Top-K / N largest or smallest elements (e.g., data analytics, leaderboard ranking, search engines)

  • Job/print queue with prioritization (e.g., print servers, ticketing systems)

  • Bandwidth management in networking (e.g., routers, firewalls, packet shapers)

Initialization

Because std::queue is a container adaptor, you have the flexibility to specify the underlying container—such as deque — at the time of priority queue creation.

2
1
std::priority_queue<int> q1;    // vector (by default)
2
std::priority_queue<int, std::deque<int>, std::less<int>> q2;

L2: std::less<int> makes it a max-heap.

Priority Queue Operations

For more information, see cppreference.com.

10
1
std::priority_queue<int> pq;    // vector
2

3
pq.push(10);
4
pq.push(20);
5
pq.push(3);
6
pq.push(4);
7

8
std::cout << pq.top();  // 20 (largest)
9
pq.pop();               // remove 20
10
pq.top();               // 10 (largest)

Project: Usage of std::priority_queue

91
1
#include <iostream>
2
#include <queue>
3

4
class person
5
{
6
public:
7
    person() : name{"Unkown"}, age{0} {}
8
    person(std::string name, int age)
9
        : name{name}, age{age}
10
    {}
11
    bool operator<(const person &rhs) const
12
    {
13
        return this->age < rhs.age;
14
    }
15
    bool operator==(const person &rhs) const 
16
    {
17
        return (this->name == rhs.name && this->age == rhs.age);
18
    }
19
    
20
private:
21
    friend std::ostream& operator<<(std::ostream &os, const person &p);
22
    std::string name;
23
    int age;
24
};
25

26
// Overloading the insertion operator as a global function.
27
std::ostream& operator<<(std::ostream &os, const person &p)
28
{
29
    os << p.name << ":" << p.age;
30
    return os;
31
}
32

33
// Prints the priority queue by repeatedly topping and popping the elements.
34
// Note that this function is passed a priority queue 'by value' so whatever
35
// happens inside this function will not affect the original priority_queue.
36
template <typename T>
37
void print(std::priority_queue<T> pq)
38
{
39
    std::cout << "[ ";
40
    while (!pq.empty())
41
    {
42
        T elem = pq.top();
43
        pq.pop();
44
        std::cout << elem << " ";
45
    }
46
    std::cout << "]" << std::endl;
47
}
48

49
// push(), size(), top(), pop()
50
void test1(void)
51
{
52
    std::cout << "\nTEST1" << std::endl;
53

54
    std::priority_queue<int> pq;
55
    for (int n : {3, 5, 7, 12, 23, 12, 4, 100, 0, 3, 5, 7})
56
    {
57
        pq.push(n);
58
    }
59

60
    std::cout << "Size: " << pq.size() << std::endl;
61
    std::cout << "Top: " << pq.top() << std::endl;
62

63
    print(pq);
64

65
    pq.pop();
66
    print(pq);
67
}
68

69
// push()
70
void test2(void)
71
{
72
    std::cout << "\nTEST2" << std::endl;
73

74
    std::priority_queue<person> pq;
75

76
    // Ordered by age (based on the overloaded 'operator<')
77
    pq.push(person{"A", 10});
78
    pq.push(person{"B", 1});
79
    pq.push(person{"C", 14});
80
    pq.push(person{"D", 18});
81
    pq.push(person{"E", 17});
82
    pq.push(person{"F", 27});
83
    print(pq);
84
}
85

86
int main(int argc, char *argv[])
87
{
88
    test1();
89
    test2();
90
    return 0;
91
}

9
1

2
TEST1
3
Size: 12
4
Top: 100
5
[ 100 23 12 12 7 7 5 5 4 3 3 0 ]
6
[ 23 12 12 7 7 5 5 4 3 3 0 ]
7

8
TEST2
9
[ F:27 D:18 E:17 C:14 A:10 B:1 ]