--- date: '2024-10-11' description: extends Boyer-Moore finding algorithm id: Misra-Gries heavy-hitters algorithm modified: 2026-06-05 15:08:20 GMT-04:00 tags: - algorithm title: Misra-Gries heavy-hitters algorithm created: '2024-10-11' published: '2024-10-11' pageLayout: default slug: thoughts/Misra-Gries-heavy-hitters-algorithm permalink: https://aarnphm.xyz/thoughts/Misra-Gries-heavy-hitters-algorithm.md generator: quartz: v4.6.0 hostedProvider: Cloudflare baseUrl: aarnphm.xyz full: https://aarnphm.xyz/llms-full.txt --- one of the earliest [[thoughts/data]] streaming algorithm. ## problem. > Given the bag $b$ of $n$ elements and an integer $k \geq 2$. Find the values that occur more than $n/k$ times in $b$ idea: two passes over the values in $b$, while storing at most $k$ values from $b$ and their number of occurrences. Assume the bag is available in array $b[0:n-1]$ of $n$ elements, then a _heavy-hitter_ of bag $b$ is a value that occurs more than $n/k$ times in $b$ for some integer $k \geq 2$ ## pseudocode.

"\\begin{algorithm}\n\\caption{Misra--Gries}\n\\begin{algorithmic}\n\\State $t \\gets \\{\\}$\n\\State $d \\gets 0$\n\\For{$i \\gets 0$ to $n-1$}\n \\If{$b[i] \\notin t$}\n \\State $t \\gets t \\cup \\{b[i]\\}$\n \\State $d \\gets d + 1$\n \\Else\n \\State $t \\gets t \\cup \\{b[i]\\}$\n \\EndIf\n \\If{$d = k$}\n \\State Delete $k$ distinct values from $t$\n \\State Update $d$\n \\EndIf\n\\EndFor\n\\end{algorithmic}\n\\end{algorithm}"

Algorithm 2 Misra--Gries

1: $t \gets \{\}$

2: $d \gets 0$

3:for $i \gets 0$ to $n-1$ do

4:if $b[i] \notin t$ then

5: $t \gets t \cup \{b[i]\}$

6: $d \gets d + 1$

7:else

8: $t \gets t \cup \{b[i]\}$

9:end if

10:if $d = k$ then

11:Delete $k$ distinct values from $t$

12:Update $d$

13:end if

14:end for