Heap LFU (Priority Queue LFU)

Feature: policy-heap-lfu

Goal

Implement LFU using a heap to choose the minimum frequency victim, trading O(1) for simpler structure and O(log n) operations.

Core Data Structures

Typical heap LFU:

• HashMap<K, V> (or store) for values
• HashMap<K, u64> authoritative frequencies
• BinaryHeap<Reverse<(u64, K)>> min-heap of (frequency, key)

In cachekit, this is implemented in src/policy/heap_lfu.rs using lazy stale entries:

• Every access pushes a new (freq, key) into the heap.
• On eviction, heap entries are popped until one matches the authoritative frequency map.

Operations

get(key)

• Increment frequencies[key]
• Push (new_freq, key) into the heap (older heap entries become stale)

insert(key, value)

• Insert/update value.
• Initialize or increment frequency.
• Push updated (freq, key) to heap.
• If at capacity: repeatedly pop heap until you find a non-stale victim; remove it from store + frequency map.

Complexity & Overhead

• get: O(log n) (heap push)
• eviction: O(log n) amortized, but may pop multiple stale entries
• memory: heap can grow beyond live entries unless you periodically rebuild

Implementation Notes

• To bound heap growth, periodically rebuild the heap from the authoritative frequency map when heap size exceeds a threshold multiple of live entries (this is the approach documented in the module).

References

• Wikipedia: https://en.wikipedia.org/wiki/Cache_replacement_policies