If every key within an iterator is duplicated 10 times, this seems like it would exponentially grow the pq. I read the min, then read 10 more into pq for the next key, and repeat indefinitely. Not only is this a memory problem, but the performance of the pq decreases with the log of its size, so it will cause some computational slowdown too.

One way to deal with this is to have the PriorityQueue not be of (K, M, iter) tuples, but rather be of (iter, List[(K, M)]) tuples (or something like that). readFromIterator would then read all of the (K, M) values of the same hash, and rather than doing pq.enqueue() for all of them, it would append them all to a list, and finally pq.enqueue() that list.

The merge function would be changed such that we read through the list and separate out the elements that have a collided hash from the actual same-keys, and finally we only readFromIterator when the List for a particular iterator is completely empty.

This approach has the advantage of keeping the size of pq bounded by the number of iterators. Additionally, it would confront collisions directly and could allow us to use a Map[K, List[M]] instead of List[(K, M)] to more efficiently distinguish between the list of same-keys and collided keys.