Approach: use the Misra–Gries (aka Frequent) algorithm to track top-k frequent items with limited memory. It maintains up to k counters; each stream element is processed in O(1) time. Misra–Gries guarantees that for any returned item i, estimated_count(i) ≤ true_count(i) and true_count(i) ≥ estimated_count(i) − n/(k+1), where n is total items seen. (If you need probabilistic bounds and point queries with overestimates, Count–Min Sketch is an alternative.)Java implementation (simple, single-threaded):java
import java.util.*;
public class MisraGriesTopK<T> {
private final int k;
private final Map<T, Integer> counters = new HashMap<>();
private long total = 0;
public MisraGriesTopK(int k) {
if (k < 1) throw new IllegalArgumentException("k>=1");
this.k = k;
}
// Process one stream item
public void add(T item) {
total++;
if (counters.containsKey(item)) {
counters.put(item, counters.get(item) + 1);
return;
}
if (counters.size() < k) {
counters.put(item, 1);
return;
}
// decrement all counters by 1 and remove zeros
List<T> toRemove = null;
for (Iterator<Map.Entry<T, Integer>> it = counters.entrySet().iterator(); it.hasNext();) {
Map.Entry<T, Integer> e = it.next();
int v = e.getValue() - 1;
if (v == 0) it.remove();
else e.setValue(v);
}
}
// Get candidate top-k with their current counters (lower bounds)
public Map<T, Integer> getCandidates() {
return new HashMap<>(counters);
}
public long totalSeen() { return total; }
}
