What is the right data structure for MST in a stream
By  noticing that $H$ remains a tree except when $H \gets H \cup (a,b)$ happens,
you can use a ST-Tree[1],  which you can easily modify to support queries of the form &quot;what is the maximum weight edge on the path from $a$ to $b$&quot;
Instead of adding $(a,b)$ directly to $H$ first you check if $a$ and $b$ are connected (using the ST-Tree or a Union-Find).
If they are not, you add it as possible. Otherwise, if its weight is smaller than $max( a \to b)$, you replace with $(a,b)$ the max. weight edge.
[1]https://en.wikipedia.org/wiki/Link/cut_tree