# 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