Weighted cache that evicts the heaviest entries

Implement WeightedCache, a key-value cache with a total-weight budget instead of an item count.

WeightedCache(max_total_weight: int)
put(key, value, weight: int) -> list   # returns the keys evicted by this call
get(key) -> value | None

Each entry has a positive integer weight. After every put, the sum of the weights of the stored entries must be at most max_total_weight.

• put inserts the key, or replaces the value and weight of a key already stored.
• If the total weight is now over the budget, evict entries with the largest weight first, one at a time, until it fits. The entry you just wrote is a candidate too. If several entries tie for the largest weight, you may evict any of them. (The reference solution evicts the one written longest ago.)
• A put whose weight is greater than max_total_weight is rejected and does not change the cache.
• get returns the stored value, or None if the key is not present.

Aim for better than a linear scan per eviction.

Constraints: up to 10^5 operations; 1 ≤ weight ≤ max_total_weight ≤ 10^9.

Example 1

c = WeightedCache(10)
c.put("a", 1, 3)   -> []        total 3
c.put("b", 2, 4)   -> []        total 7
c.put("c", 3, 5)   -> ["c"]     total would be 12; "c" is heaviest
c.get("c")         -> None

Example 2 (continuing)

c.put("d", 4, 2)   -> []        total 9
c.put("a", 9, 6)   -> ["a"]     the update makes "a" weight 6, total 12
c.put("e", 5, 4)   -> []        b4 + d2 + e4 = 10
c.put("f", 6, 1)   -> ["b"]     total 11; "b" and "e" tie at 4