Lazy Heap Index (Heap + Authoritative Map)

What It Is

A “lazy heap” pattern keeps:

• an authoritative map of current scores, and
• a heap of (score, key) snapshots that may contain stale entries

On pop(), you discard stale heap entries until the top matches the authoritative score.

Used for:

• heap-based LFU
• OPT trace simulators (next-use position)
• TTL expiry heaps (expires_at)
• size/cost-aware eviction heaps (GDS/GDSF-like scores)

Core Types

• scores: HashMap<K, Score> (authoritative)
• heap: BinaryHeap<Reverse<(Score, K)>> (min-heap) or max-heap depending on policy

Operations

• update(key, new_score):
  • scores[key] = new_score
  • heap.push((new_score, key))
• pop_best():
  • loop pop heap:
    • if (score, key) matches scores[key], accept it
    • else discard and continue

Complexity

• update: O(log n)
• pop_best: O(log n) amortized, but can do multiple pops if many stale entries exist

Bounding Stale Growth

If heap.len() grows much larger than scores.len(), rebuild:

• clear heap
• push one entry per scores item

This keeps memory bounded and improves worst-case pop latency.