Skip to content
CCC Python Course

Heaps and lazy deletion; ordered-set substitutes

Stage
5
Module
M5.11
Lessons
1

In this module

  • Implement min-heaps and max-heaps using heapq and negation.
  • Detect and skip out-of-date entries using validity checks.
  • Simulate multiset operations and keep running aggregates.
  • Maintain a sliding window minimum using a lazy-deletion deque.

Before this module

M4.2Sorting with keys, and greedyM4.1Hash-based lookup

Lessons

  1. 1Heaps and lazy deletion; ordered-set substitutes

Practice

Try these on the judge. Each link opens the problem on WMOJ.

  1. 2021 S4
    Daily Commute (opens on WMOJ in a new tab) WMOJ

    Find the minimum of dynamic expressions using lazy-deletion heaps to track candidates.

  2. 2025 S3
    Pretty Pens (opens on WMOJ in a new tab) WMOJ

    Track the best combination of items in a changing collection under updates.

    Why DMOJ: A greedy problem over a changing collection, solved with heaps and lazy deletion.