# Heap allowing to remove items

Maintain a set, allowing to add or remove elements and to query the smallest element.

# Heap

Such a data structure is usually implemented by a heap. Heaps are binary trees, where every node stores a smaller value than its descendants. The heaps available in the standard libraries usually only allow to insert items.

Hence you have two possibilities:

- implement your own heap with a removal operation,
- augment a standard heap with lazy removals.

# Lazy removals

The later option is much simpler to implement. Simply mark elements to be removed, and remove them only once they appear as the top element of the heap. Since the heap can store multiple copies of the same item, we use a counter to mark items. It simply stores how many copies of a given item have to removed.

The price for this simple implementation is a larger worst case complexity of the operations. If your heap contains n elements plus k elements still to be removed, then the operations have time complexity O(log(n + k)). Implementing your own heap with a real removal operator, allows to achieve complexity O(log n) per operation. However for most problems in programming competitions, the lazy removals are good enough.