Lazy Heap: Lazy Deletion

A lazy heap is a heap-based priority queue that delays some operation on heaps like deletions, merges, or structural cleanup, to future operations in order to simplify implementation or avoid time limit exceeded. This “do it later” strategy comes at the cost of slightly worse worst-case bounds or extra memory for simpler code and often faster execution in practice.

What is Lazy heap?

A lazy heap is a heap variant where certain operations are postponed until it is absolutely necessary. Instead of eagerly fixing the heap after every update, a lazy heap records pending changes and executes them up only when they affect operations like top or pop.

Common types of laziness includes:

• Lazy deletion: Mark elements as deleted and physically remove them only when they reach the top of the heap.
• Lazy merging: Splice two heap root lists together in O(1) and consolidate later, as in lazy binomial or Fibonacci heaps.
• Lazy consolidation: Avoid tree-linking in multi-tree heaps until an extract-min forces cleanup

Here we will cover most frequently used lazy technique, i.e. Lazy deletion with the help of java's PriorityQueue.

public class LazyHeap<T>{
    private int size;
    private PriorityQueue<T> heap;
    private Map<T, Integer> removed;

    public LazyHeap(){
        heap = new PriorityQueue<T>();
        removed = new HashMap<>();
        size = 0;
    }

    public LazyHeap(Comparator<T> c){
        heap = new PriorityQueue<>(c);
        removed = new HashMap<>();
        size = 0;
    }

    public int size(){return size;}
    public T poll(){
        T obj=peek();
        remove(obj);
        return obj;
    }
    public T peek(){
        while(removed.getOrDefault(heap.peek(),0)>0){
            T r=heap.poll();
            removed.put(r,removed.get(r)-1);
        }
        return heap.peek();
    }
    public void add(T obj){
        size++;
        heap.add(obj);
    }
    public void remove(T obj){
        size--;
        removed.put(obj,removed.getOrDefault(obj,0)+1);
    }
}

The class maintains three key fields:

• PriorityQueue<T> heap: Standard min-heap storing all elements (live + marked-deleted).
• Map<T, Integer> removed: Tracks removal counts for each element using getOrDefault(num, 0) + 1.
• int size: Logical count of live elements (increases on add, decreases on remove).

Key Operations

add(T obj)

public void add(T obj){
    size++;  // Logical size increases
    heap.add(obj);  // Push to heap
}

Simply adds to both logical size and physical heap in O(logn) time. No validation is done here, just simple add to heap.

remove(T obj)

public void remove(T obj){
    size--;  // Logical size decreases immediately
    removed.put(obj, removed.getOrDefault(obj,0)+1);  // Mark as deleted
}

The remove() method updates counters in O(1) expected time (HashMap) without touching the heap structure. Multiple calls to remove the same element are handled by the counter, where as a real deletion in heap structure would have costed us O(logn) time.

peek()

public T peek(){
    while(removed.getOrDefault(heap.peek(),0)>0){  // While top is marked deleted
        T r=heap.poll();  // Physically remove it
        removed.put(r, removed.get(r)-1);  // Decrease counter
    }
    return heap.peek();  // Now top is real top of the heap
}

The cleanup in heap structure happens here, where all delete elements are removed from heap. Repeatedly pops already marked as removed top elements until finding a real top element that is not marked as removed. The overall time low if deletions don't cluster at the top.

poll()

public T obj=peek();  // Triggers cleanup, gets live minimum
remove(obj);  // Marks it as deleted (logical removal)
return obj;

This method combines peek() cleanup with logical removal of the top element.

Sample problems to practice

• Leetcode 480. Sliding Window Median
• Leetcode 295. Find Median from Data Stream

Thanks for reading, stay tuned!