↵
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.↵
↵
↵
```cpp↵
#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↵
}↵
↵
↵
###
↵
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.↵
↵
```python↵
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↵
```↵
↵
### 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. ↵
