# Priority queue with unique elements and sublinear time merge?

Some priority queues, like the height-based leftist tree (or here) support merging in $\mathcal O\left(\log n\right)$ time.

I am looking for a priority queue that merges in (expected|average|amortized|worst-case) sub-linear time, but also has the following properties:

• Elements are unique
• peek and pop should work in (expected|average|amortized|worst-case) sub-linear time

Is this impossible?

• Which of the properties the leftist tree does not support? Nov 1, 2013 at 13:53
• @MahmoudAlimohamadi I don't think the elements must be unique; ie. if you merge two trees containing some of the same elements, you end up with duplicates. Nov 1, 2013 at 14:52

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>1$. We split into two cases depending on whether $a < \lg^2 n$.

If $a < \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 > \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)$.

• Awesome, this seems like a great answer, exactly what I was looking for. Like your other comment, I felt "doesn't seem likely" to be unconvincing, and I suspected some crazy contraption (like this one) might give better results. I just have to spend some time reviewing it until I understand it :D. Great work. Nov 4, 2013 at 3:36

How about using a Strict Fibonacci Heap? - Here are the worst-case complexities:

$$\mathcal{O}(1) \text{ find-min}$$ $$\mathcal{O}(\log_2 n) \text{ delete-min}$$ $$\mathcal{O}(1) \text{ insert}$$ $$\mathcal{O}(1) \text{ decrease-key}$$ $$\mathcal{O}(1) \text{ merge}$$

Brodal, Gerth Stølting, George Lagogiannis, and Robert E. Tarjan. “Strict Fibonacci Heaps.” In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, 1177–84. STOC ’12. New York, NY, USA: ACM, 2012. doi:10.1145/2213977.2214082.

PS: I am not 100% sure how it works with unique elements, but I'd imagine that if it's unsupported it'd be trivial to add onto the delete-min step; at $\mathcal{O}(k \log_2 n)$. Or maintain a hashtable also, to remove the $k$ term at the insert step.

• This does not answer the question. Mar 16, 2015 at 3:13
• Well you are right in that it isn't merging in sublinear time… however constant time isn't bad, and if you define a relationship between $O(1)$ and $o(1)$ you can come to a sublinear result.
– A T
Mar 16, 2015 at 4:10
• I don't think you can get a sublinear result out of this. I doubt that there is a mathematically sound way to "define a relationship between $O(1)$ and o(1)\$" other than the existing definitional relationship between them such that you get anything like what the questioner is asking for. Mar 16, 2015 at 6:01