Tutorial: Lazy Deletion with Priority Queue (C++ & Python)

Hi everyone! I'm Eman, and this is my very first blog on Codeforces. Today, I'd like to share a simple tutorial on Lazy Deletion using a Priority Queue.

The Problem: Why do we need this?

Normally, you cannot delete an element from the middle of a priority queue. You can only delete the top element. However, in many competitive programming problems, we need to add elements, get the maximum (or minimum) element, and delete specific elements quickly.

The Idea: Lazy Deletion

Instead of looking for the element to delete it right away, we delay the deletion! We do not point to the element to delete it. Instead, we record in another place that it is deleted. When this element reaches the top of the priority queue, only then we delete it.

One way to do this is to create two priority queues:

1. A main priority queue for the elements, called pq.

2. A second priority queue to put the elements you want to delete in, called deleted_pq.

How to handle the operations:

• When you add an element: you push it into pq.

• When you want to delete an element: you push it into deleted_pq.

• When you want to get the largest element in the main pq: you use a while loop to compare the top of pq with the top of deleted_pq. If they are equal, this means the element is deleted, so you pop from both of them. We repeat this until the top element in the main queue is not a deleted element.

C++ Code

Here is the C++ implementation. It is very useful if you want to avoid the slow constant factor of std::multiset when you only need to add, delete, and get the maximum element.

#include <iostream>
#include <queue>

using namespace std;

priority_queue<int> pq;
priority_queue<int> deleted_pq;

// Function to clean the top from deleted elements
void clean_top() {
    // While both tops are equal, the current element is deleted
    while (!pq.empty() && !deleted_pq.empty() && pq.top() == deleted_pq.top()) {
        pq.pop();
        deleted_pq.pop();
    }
}

void add_element(int x) {
    pq.push(x);
}

void remove_element(int x) {
    deleted_pq.push(x);
}

int get_max() {
    clean_top(); // Clean the top first
    if (!pq.empty()) {
        return pq.top();
    }
    return -1; // If the queue is empty
}

Why is this important for Python?

This trick is a lifesaver for Python users in Competitive Programming. Python does not have a built-in multiset. If you use list.remove() to delete an element, it takes $$$O(N)$$$ time, which often leads to Time Limit Exceeded (TLE).

By using Lazy Deletion with the heapq library, you can add, remove, and get the maximum/minimum in just $$$O(\log N)$$$ time.

Important Note: The heapq library in Python is a Min-Heap by default. To make it work as a Max-Heap (like the C++ example), we multiply the elements by -1 when adding them, and multiply by -1 again when we get them.

import heapq

pq = []
deleted_pq = []

def clean_top():
    # Compare the smallest element (which is the largest absolute value)
    while pq and deleted_pq and pq[0] == deleted_pq[0]:
        heapq.heappop(pq)
        heapq.heappop(deleted_pq)

def add_element(x):
    # Multiply by -1 to simulate a Max-Heap
    heapq.heappush(pq, -x)

def remove_element(x):
    # Record the element in the deleted list the same way
    heapq.heappush(deleted_pq, -x)

def get_max():
    clean_top() # Make sure the current top is not deleted
    if pq:
        return -pq[0] # Multiply by -1 again to get the original value
    return -1

Time Complexity Summary:

• Add: $$$O(\log N)$$$
• Lazy Remove: $$$O(\log N)$$$
• Get Max: $$$O(\log N)$$$ (Amortized)

I hope this tutorial is clear and helpful.