Home | Projects | Notes > Data Structures & Algorithms > Priority Queues

Priority Queues

Introduction

A priority queue is an abstract data structure where each element has a priority, and elements are served based on their priority, not their insertion order.

• By default, the highest priority (usually the largest number) is dequeued first.

• Internally, it’s typically implemented using a binary heap for efficient performance.

Pros:

• Efficient operations: push, pop, and top all run in O(log n) time with a binary heap.

• Dynamic ordering: Automatically keeps the highest (or lowest) priority item at the top.

• Flexible: Can be implemented as min-heap or max-heap, or customized using comparators.

• Widely used: Great for scheduling, graph algorithms (e.g., Dijkstra’s), load balancing, etc.

Cons:

• Limited access: You can only access or remove the top-priority element — no direct access to arbitrary items.

• Not suitable for sorted traversal: Unlike balanced BSTs, you can’t iterate in order.

• Re-prioritizing an item (i.e., decreasing key) is not efficient unless custom logic is added.

Usage

• Task scheduling

• Shortest path algorithms

• Simulations or real-time systems

• Event-driven systems

Implementation (C++)

Header (minpq.hpp)

26
1
#ifndef MINPQ_HPP
2
#define MINPQ_HPP
3

4
#include <vector>
5

6
class minpq
7
{
8
public:
9
    void push(const int val);
10
    void pop();
11
    int top() const;
12
    bool empty() const;
13
    int size() const;
14
    void print() const;
15

16
private:
17
    std::vector<int> heap;  
18

19
    int parent(const int i) const;
20
    int left(const int i) const;
21
    int right(const int i) const;
22
    void heapify_up(int idx);
23
    void heapify_down(int idx);
24
};
25

26
#endif

Source (minpq.cpp)

104
1
#include "minpq.hpp"
2
#include <iostream>
3
#include <stdexcept>
4

5
void minpq::push(const int val)
6
{
7
    heap.push_back(val);
8
    heapify_up(heap.size() - 1);
9
}
10

11
void minpq::pop()
12
{
13
    if (heap.empty())
14
    {
15
        throw std::underflow_error("MinHeap is empty");
16
    }
17

18
    heap[0] = heap.back();
19
    heap.pop_back();
20

21
    if (!heap.empty())
22
    {
23
        heapify_down(0);
24
    }
25
}
26

27
int minpq::top() const
28
{
29
    if (heap.empty())
30
    {
31
        throw std::underflow_error("MinHeap is empty");
32
    }
33

34
    return heap[0];
35
}
36

37
bool minpq::empty() const
38
{
39
    return heap.empty();
40
}
41

42
int minpq::size() const
43
{
44
    return heap.size();
45
}
46

47
void minpq::print() const
48
{
49
    for (int val : heap)
50
    {
51
        std::cout << val << " ";
52
    }
53

54
    std::cout << std::endl;
55
}
56

57
// private functions
58

59
int minpq::parent(const int i) const
60
{
61
    return (i - 1) / 2;
62
}
63

64
int minpq::left(const int i) const
65
{
66
    return 2 * i + 1;
67
}
68

69
int minpq::right(const int i) const
70
{
71
    return 2 * i + 2;
72
}
73

74
void minpq::heapify_up(int idx)
75
{
76
    while (idx > 0 && heap[parent(idx)] > heap[idx])
77
    {
78
        std::swap(heap[parent(idx)], heap[idx]);
79
        idx = parent(idx);
80
    }
81
}
82

83
void minpq::heapify_down(int idx)
84
{
85
    int smallest = idx;
86
    int l = left(idx);
87
    int r = right(idx);
88

89
    if (l < heap.size() && heap[l] < heap[smallest])
90
    {
91
        smallest = l;
92
    }
93

94
    if (r < heap.size() && heap[r] < heap[smallest])
95
    {
96
        smallest = r;
97
    }
98

99
    if (smallest != idx)
100
    {
101
        std::swap(heap[idx], heap[smallest]);
102
        heapify_down(smallest);
103
    }
104
}

Test Driver

32
1
#include <iostream>
2
#include "minpq.hpp"
3

4
int main(int argc, char *argv[])
5
{
6
    minpq pq;
7

8
    pq.push(30);
9
    pq.push(10);
10
    pq.push(40);
11
    pq.push(50);
12
    pq.push(20);
13
    pq.push(60);
14

15
    std::cout << pq.top() << std::endl; // 10
16

17
    pq.pop();
18

19
    std::cout << pq.top() << std::endl; // 20
20

21
    pq.print(); // 20 30 40 50 60
22

23
    pq.pop();
24

25
    pq.print(); // 30 50 40 60
26

27
    std::cout << pq.empty() << std::endl;   // 0
28
    std::cout << pq.size() << std::endl;    // 4
29

30
    return 0;
31
}
32

6
1
10
2
20
3
20 30 40 50 60
4
30 50 40 60
5
0
6
4