Misra-Gries heavy hitters algorithm

The Misra-Gries heavy hitters algorithm finds the values that occur more than n divided by k times in a bag of n elements, for an integer k of at least 2. Misra and Gries defined the heavy-hitters problem, though they did not use that term, and described the first algorithm for it in the paper Finding repeated elements. The algorithm extends the Boyer-Moore majority finding algorithm. It makes two passes over the data while storing at most k values and their counts. The first pass builds a k-reduced bag, produced by repeatedly deleting k distinct elements, which must contain every heavy hitter because a k-reduced bag holds fewer than k different values; the second pass counts the surviving candidates and keeps those that really exceed n divided by k. With an AVL tree the running time is O(n log k), and the storage for O(k) value and counter pairs is O(k (log n + log m)) bits. It is one of the earliest streaming algorithms, and its first-pass output is called a Misra-Gries summary.