Priority Queue

06 Oct 2024

1. Introduction

A priority queue is a data structure that can quickly retrieve the current highest-priority element. A normal queue removes elements in insertion order, while a priority queue removes them according to priority.

In C++, a priority queue is usually implemented with a heap:

By default, it is a max-heap: each removal gives the largest current element.
Using greater<int> creates a min-heap: each removal gives the smallest current element.

It is useful when a problem repeatedly inserts elements and repeatedly needs the current minimum or maximum.

2. Basic Usage

#include <bits/stdc++.h>
using namespace std;

priority_queue<int> maxHeap; // Max-heap: top() is the largest value
priority_queue<int, vector<int>, greater<int> > minHeap; // Min-heap: top() is the smallest value

The most common operations are:

q.push(x)  // Insert x
q.top()    // Read the top element without removing it
q.pop()    // Remove the top element
q.empty()  // Check whether the queue is empty
q.size()   // Get the number of elements

Insertion and removing the top both take O(log n), while reading the top takes O(1). This lets us keep finding the current minimum or maximum without sorting the entire collection after every change.

3. Examples

Example: Luogu P3378: Heap Template

This basic priority-queue problem has three operations: insert a value, print the current minimum, and remove the current minimum.

These are exactly the fundamental min-heap operations push, top, and pop. Once a min-heap is created with greater<int>, its top is always the smallest current value.

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    cin >> n;

    priority_queue<int, vector<int>, greater<int> > q;
    while (n--) {
        int op;
        cin >> op;

        if (op == 1) {
            int x;
            cin >> x;
            q.push(x);
        } else if (op == 2) {
            cout << q.top() << '\n';
        } else {
            q.pop();
        }
    }
    return 0;
}

A priority queue does not fully sort every element. Instead, it maintains the one element that currently matters most. When a problem repeatedly asks for the greatest, smallest, or otherwise best available choice, a priority queue is often a direct and efficient tool.

Priority Queue

Related Posts