Sign up ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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?

share|cite|improve this question
Which of the properties the leftist tree does not support? – Mahmoud A. Nov 1 '13 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. – Realz Slaw Nov 1 '13 at 14:52

2 Answers 2

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)$.

share|cite|improve this answer
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. – Realz Slaw Nov 4 '13 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.

share|cite|improve this answer
This does not answer the question. – jbapple Mar 16 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 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. – jbapple Mar 16 at 6:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.