Misra–Gries heavy hitters algorithm

<a href="/facts/Jayadev_Misra/nfgR4Lw3">Misra</a> and <a href="/facts/David_Gries/36zCYJT8">Gries</a> defined the heavy-hitters problem
(though they did not introduce the term heavy-hitters) and described the first algorithm
for it in the paper Finding repeated elements. Their algorithm
extends the <a href="/facts/Boyer%25E2%2580%2593Moore_majority_vote_algorithm/TjAw3Csw">Boyer-Moore majority finding algorithm</a>
in a significant way. 
One version of the heavy-hitters problem is as follows: Given is a
<a href="/facts/Bag/JB87dfvV">bag</a> b of n elements and an integer k ≥ 2. Find the values that
occur more than n ÷ k times in b. The Misra-Gries algorithm solves
the problem by making two passes over the values in b, while storing
at most k values from b and their number of occurrences during the
course of the algorithm.
Misra-Gries is one of the earliest <a href="/facts/Streaming_algorithm/BjSCe5rR">streaming algorithms</a>,
and it is described below in those terms in section #Summaries.

Misra–Gries heavy hitters algorithm open-in-new

Misra–Gries heavy hitters algorithm