Priority queue with unique elements and sublinear time merge?
Keep your elements in linked lists of buckets. Buckets will have size $O(\lg^2 n)$ when stored in a list with $n$ total elements. Buckets are stored as balanced search trees with $O(\lg n)$ insert (and, since each bucket has size $O(\lg^2 n)$, this is actually $O(\lg \lg n)$), $O(1)$ extractMin, $O(n+m)$ merge, $O(\lg n)$ split, and no duplicates. The liked list should be sorted by the size of the buckets, though not their key values.

To maintain the bucket invariant, we need to occasionally combine or split buckets. To pay for this, we assign each priority queue a potential. This lets us use the physicist's amortization.

Each bucket will be assigned a potential of $0$ if it has size within $1$ of $\lg^2 n$ and a potential of $c \lg^2 n$ if it is size $\lg^2 n/d$ or $d \lg^2 n$ (for constants $c$ and $d$ to be determined later), varying bitonicly and linearly in the size of the bucket.

The tricky method is merge. Assume we are merging two lists of size $n$ and $an$, for $a&gt;1$. We split into two cases depending on whether $a &lt; \lg^2 n$.

If $a &lt; \lg^2 n$, then we join the lists by merging them like in merge sort, so that the buckets stay sorted by size. Since the buckets have size $O(\lg^2 n)$, the linked lists have length $O(n/\lg^2 n)$ and $O(an/\lg^2 an)$, so merging them takes time $O(an/\lg^2 an)$ which is $o(an)$, and so is sublinear.

It also may increase the potential. Each bucket gets at most $O(\lg^2 (1+a)n - \lg^2 n) = O(\lg^2 (1+a) + \lg n \lg (1+a))$ closer to criticality. This is $O(\lg n \lg \lg n)$, and there are $O(an/\lg^2 an)$ buckets, so the increase in potential is at most $O(an \lg n \lg \lg n/\lg^2 an)$, which is $o(an)$ and thus sublinear.

Finally, we traverse the head and tail of the list, splitting and joining supercritical buckets until no supercritical buckets are left. This is "free", paid for by the potential we release. (To place them properly, we need to maintain a finger to the point in the list where buckets are exactly the right size. This is $O(1)$ extra work on each operation.)

If $a &gt; \lg^2 n$, we destroy the smaller priority queue and insert its items one-by-one into the larger queue. As long as insert is $o(\lg^2 n)$ amortized, this is sublinear.

Insert adds an element to the smallest bucket. This increases its potential by at most $O(1)$ and increases the potential of the rest of the buckets by at most $O(\lg^2 (n+1) - \lg^2 n) = O(\lg n/n)$. Since there are $O(n/\lg^2 n)$ buckets, the total increase in potential is $O(1/\lg n)$. If the smallest bucket is large, some splitting may be required, but this is amortized free (paid for by the potential we get back). The total amortized cost of insert is thus the cost to insert it into a bucket, which is $O(\lg \lg n)$.

extractMin traverses the bucket list and identifies the buckets with minimum key. It removes the minimum key from each of these buckets, rearranging the bucket list as necessary to maintain order. The total structure size may change by $O(n/\lg^2 n)$ if we remove a key from each bucket. This induces a potential change of at most $O(\lg n)$ in each bucket, for a total potential change of $O(n/\lg n)$. The traversal and removal take time linear in the number of buckets, which is $o(n)$.

Note that these operations, including an extractMin that extracts every copy of the minimum, are sublinear in the number of elements, not the number of unique elements. The number of unique elements in a priority queue of size $n$ may be as low as $\Theta(\lg^2 n)$.