# Does there exist a priority queue with $O(1)$ extracts?

There are a great many data structures that implement the priority-queue interface:

• Insert: insert an element into the structure
• Get-Min: return the smallest element in the structure
• Extract-Min: remove the smallest element in the structure

Common data structures implementing this interface are (min)heaps.

Usually, the (amortized) running times of these operations are:

• Insert: $\mathcal{O}(1)$ (sometimes $\mathcal{O}(\log n)$)
• Get-Min: $\mathcal{O}(1)$
• Extract-Min: $\mathcal{O}(\log n)$

The Fibonacci heap achieves these running times for example. Now, my question is the following:

Is there a data structure with the following (amortized) running times?

• Insert: $\mathcal{O}(\log n)$
• Get-Min: $\mathcal{O}(1)$
• Extract-Min: $\mathcal{O}(1)$

If we can construct such a structure in $\mathcal{O}(n)$ time given sorted input, then we can for instance find line intersections on pre-sorted inputs with $o\left(\frac{n}{\log n}\right)$ intersections strictly faster than if we use the 'usual' priority queues.

• I think using a balanced BST, that would not rebalance when doing Extract-Min could work. Or maybe a skip list. – svick Mar 20 '12 at 1:11
• @svick: skip lists are randomized, which is not what I'm looking for. If you can do it with a BST, then that's great, but I think you will have to do some kind of balancing. – Alex ten Brink Mar 20 '12 at 1:36
• On a side note: this is a seeding question and I know the answer, but it's nice to see that it's not so easily solved. If anyone knows the answer, don't hesitate to give it :) – Alex ten Brink Mar 20 '12 at 1:40
• If you are accepting amortized update times, then you can keep your standard heap structures, and only make minor modifications to your analysis. See my answer below. – Joe Apr 17 '12 at 19:59

Our idea is to use threaded splay trees. Other than the Wikipedia article we will thread the trees so that every node has a pointer next to its successor in the in-order traversal; we also hold a pointer start to the smallest element in the tree.

It is easy to see that extracting the smallest element is possible in (worst case) time $\mathcal{O}(1)$: just follow the start pointer, remove the minimum and change the pointer to the minimum's next. The minimum can never have a left child; if it has a right child, we put it in the minimum's place in the tree. We do not perform the splay operation splay trees usually would do.
The result is a search tree that is still reasonably balanced: because we only remove nodes on the left flank, we know that when the number of nodes (in an affected subtree) drops to about half the original number because of deletions, the (sub)tree's height is reduced by one.

Insertions are possible in $\mathcal{O}(\log n)$ amortised time; the zig-zag (and what not) operations will here also rebalance the tree nicely.

This is a rough sketch at best. Credits go to F. Weinberg who puzzled over the question with me and our advisor M. Nebel who mentioned splay trees, about the only tree variant we had not tried.

• It's not clear to me how to get the amortized analysis to work if you don't splay on extractMin. Can you give a hint? – jbapple Mar 23 '12 at 1:38
• We have not done it in detail. The idea is that series of extract-min operations do not unbalance the tree, therefore no splaying is necessary and the normal analysis should work for insertions. – Raphael Mar 23 '12 at 7:52
• Careful! Splay trees are not necessarily balanced. Nodes that haven't been accessed in a long time may be very deep in the tree. To make the analysis go through, you have to argue in terms of the same potential function used to analyze splays. – JeffE Apr 17 '12 at 18:24
• Insert: $\mathcal{O}(\log n)$
• Get-Min: $\mathcal{O}(1)$
• Extract-Min: $\mathcal{O}(1)$

### Amortized Time

Simple implementations of a priority queue (e.g. any balanced BST, or the standard binary min-heap) can achieve these (amortized) running times by simply charging the cost of Extract-Min to insert, and maintaining a pointer to the minimum element. For example, you could have a potential function that is $cn \log n$. Then inserting a new element increases potential by $O(\log n)$, and so the amortized cost of insert is still $O(\log n)$, but Extract-Min() decreases the potential by $\Omega(\log n)$, and so the amortized cost is only $O(1)$.

### Worst-Case

You can use an existing data structure in the literature: finger-search trees, and simply maintain a pointer to the minimum element. See this survey for an overview, and the 1988 paper by Levcopoulos and Overmars for an implementable version that meets your needs.

• How very sneaky. You're right, I guess I should have demanded something stronger to exclude this. Nice idea :) – Alex ten Brink Apr 17 '12 at 20:09
• @AlextenBrink You could of demanded worst-case $O(1)$ deletions. (which seems to be what some of the other answers were going for) I added a paragraph to my answer to address that case. – Joe Apr 17 '12 at 20:28

2-4 trees have amortized $O(1)$ modifications at known locations. That is to say, if you have a pointer to some location in the tree, you can remove or add an element there in $O(1)$ amortized time.

You can thus just keep a pointer to the minimum element and the root node in a 2-4 tree. Inserts should go through the root node. Updating the pointer to the minimum is trivial after a deleteMin, and deleteMins are $O(1)$ (amortized) time.

An interesting side note: red-black trees are just a way of looking at 2-4 trees. The designers of the C++98 standard expected library implementers to supply a red-black-tree-based container, and the standard specifies that insert and delete should be $O(1)$ amortized time at known locations (which they call "iterators"). However, this is actually much trickier for red-black trees than for 2-4 trees, since it requires lazily marking nodes that need to be recolored. To my knowledge, no implementations of the C++98 standard library met that particular requirement.

By request, here is the structure I found after I formulated the question:

The basic idea is to use a threaded Scapegoat tree along with a pointer to the minimum (and for good measure, the maximum as well). A simpler alternative to threading is maintaining predecessor and successor pointers in every node (which is equivalent, simpler, but has more overhead). I've come to call it a Scapegoat heap, just to give it some name.

Just this basic structure gives you these operations:

• Search: given a key, returns a pointer to the corresponding node in $\mathcal{O}(\log n)$ time.
• Insert: given a key, inserts the key into the structure, returning a pointer to that node in $\mathcal{O}(\log n)$ time.
• Predecessor/successor: given a pointer, returns the successor or predecessor in $\mathcal{O}(1)$ time.
• Get-Min/Max: returns the pointer to the minimum or maximum.

In the analysis of Scapegoat trees, the balancing overhead of deletion is analyzed as $\mathcal{O}(\log n)$, but the analysis actually gives a balance overhead of $\mathcal{O}(1)$ (which is ignored in the paper as they also count the $\mathcal{O}(\log n)$ time it takes to find the node that is to be deleted). So, if we have a pointer to a node, we can delete it in constant time (you can do this in threaded binary search tree in $\mathcal{O}(1)$ time) and combined with the $\mathcal{O}(1)$ overhead of balancing, this gives a $\mathcal{O}(1)$ time delete:

• Delete: given a pointer, deletes the node in $\mathcal{O}(1)$ time.

Combining this:

• Extract-Min/Max: deletes the minimum/maximum node in $\mathcal{O}(1)$ time.

You can do a bit more with pointers: for instance it's not hard to maintain a pointer to the median or some other order statistic, so you can maintain a constant number of such pointers if you need them.

Some other things:

• Construct: given $n$ keys in sorted order, build a Scapegoat heap in $\mathcal{O}(n)$ time.
• Balance: balance the tree so it forms a perfectly balanced binary search tree (reduces overhead of searching) in $\mathcal{O}(n)$ time (you can do this a constant factor faster than the paper suggests by the way, by making use of predecessor/successor pointers).

And finally, I'm pretty sure you can support these operations, but I need to think about these a bit more before knowing this for sure:

• Insert-New-Min/Max: given a key that is smaller/larger than any key already in the structure, inserts the key into the structure, returning a pointer to that node in $\mathcal{O}(1)$ time.
• The key insight is that scapegoat trees assure you that deleting any node without rebalancing does not affect the performance of other operations in the long run, even if you delete many nodes. – Raphael Mar 20 '12 at 14:54
• I know of two ways of doing deletions in scapegoat trees. One way mirrors inserts, and is $O(\lg n)$ amortized time. The other way I have heard of uses global rebuilding and is $O(1)$ amortized, but I don't know how to maintain threading in that case. Imagine inserting a new key into a part of the tree that is all deleted keys yet to be removed. How do you find the predecessor of the to-be-inserted key in $O(\lg n)$ time? – jbapple Mar 26 '12 at 4:01
• @jbapple: there are two variations on how to do deletes in $O(1)$ time for Scapegoat trees. One is to leave the node in, mark it as deleted and remove all these deleted nodes with the global rebuild, and the other is to really remove the node. The first is easier to analyze (and also gives you the bound on the second, which is why it's usually explained) but the second is the one I'm after: you can delete in $O(1)$ time in a vanilla binary search tree if you can do predecessor/successor queries in $O(1)$ time, and balancing in $O(1)$ time amortized gives you the rest of the bound. – Alex ten Brink Mar 26 '12 at 13:28
• Ah, I understand now. – jbapple Mar 30 '12 at 4:08

Okay, finally got you the complexity you were looking for, and what's best, I found it in the literature:

## Worst-Case Complexity

Delete: $\bf\mathcal{O}(1)$

Delete-min: $\bf\mathcal{O}(1)$

Find-min: $\bf\mathcal{O}(1)$

Insert: $\bf\mathcal{O}(log\ n)$

## Reference

IF MELD is allowed to take linear time it is possible to support DELETE-MIN in worst case constant time by using the finger search trees of Dietz and Raman . By using their data structure MAKEQUEUE, FINDMIN, DELETEMIN, DELETE can be supported in worst case time $\mathcal{O}(1)$, INSERT in worst case time $\mathcal{O}(log\ n)$ and MELD in worst case time $\mathcal{O}(n)$.

Brodal, Gerth Stølting. ‘Fast Meldable Priority Queues’. In Proceedings of the 4th International Workshop on Algorithms and Data Structures, 282–290. WADS ’95. London, UK, UK: Springer-Verlag, 1995.

Though this uses the RAM model of computation:

Our data structure uses the random-access machine (RAM) model with unit-cost measure and logarithmic word size;

More recently, a Pointer-Machine model of computation solution has been given.

A soft heap is a subtle modification of a binomial queue. The data structure is approximate with an error parameter $\epsilon$. It supports insert, delete, meld and findmin. The amortized complexity of each operation is $O(1)$, except for insert which takes $\log (1/\epsilon)$ time. The novelty of the soft heap is in beating the logarithmic bound on the complexity of a heap in the comparison-based model. In order to break the information theoretic barrier, the entropy of the data structure is reduced by artificially raising the values of some keys. This is called corrupting the keys. The data structure is fully pointer-based (no arrays nor numeric assumptions) and is optimal for any value of $\epsilon$ in the comparison-based model.

The applications of the soft heap include computing the minimum spanning tree for a graph, dynamically maintaining percentiles and linear time order statistics. It can be also used for approximate computation, such as approximate sorting where the rank of an element never differs by more than $\epsilon n$ from the true rank.

For the original, clear and nicely written paper, see Bernard Chazelle, The Soft Heap: An Approximate Priority Queue with Optimal Error Rate, Journal of the ACM, 47(6), pp. 1012-1027, 2000. For alternative implementation and analysis that claims to be simpler and more intuitive from SODA'09, see Kaplan H. & Zwick U., A simpler implementation and analysis of Chazelle's soft heaps, 2009.

• Although a highly interesting datastructure, soft heaps are not exact: findmin may return a value that is not the minimum, but is merely an approximate minimum. Thanks for the links anyway :) – Alex ten Brink Jul 28 '12 at 10:27
• @AlextenBrink: the point of the data structure (like of many probabilistic algorithms) is that you can use an approximate data-structure to get exact answers. Indeed the approximate nature of soft heaps did not prevent it from being used in the only known linear time algorithm for minimum spanning tree. – Jérémie Jul 28 '12 at 23:00

Approaching this problem by maintaining two data-structures: an Array and a Binary Tree.

To maintain indexing in the array, previously you'd have the $\Omega(\dfrac{\log n}{\log\log n})$ bound; but more recently this has been overcome by modifying the analysis from the chronogram technique. The new [lower] $\Omega(\log n)$ bound has been proved for similar problems in the cell-probe model 1. From reading that article; it is my understanding that that bound applies to the list representation problem also.

Now if you thread a binary tree into your array and rebalance+reindex every $\mathcal{O}(\log n)$ updates, then you'll have: $\mathcal{O}(\log n)$ complexities.

Your longest run—over null deleted elements—will be $\mathcal{O}(\log n)$. This clearly leaves no theoretical advantage over rebalancing+reindexing every update.

Depending on your distribution, you can make an assumption to only rebalance every insert; thus pull the complexity out of extract. Extract—from either end—will then only take $\mathcal{O}(1)$; as no reindex needs to occur (just keep track of index offsets to keep it in $\mathcal{O}(1)$).

If you can't make that assumption, them my approach will leave you with $\mathcal{O}(\log n)$ insert, rebalance, and extract. It does have an advantage over some other approaches though, in that you can get min/max and anywhere in-between—e.g.: give me the median value—in $\mathcal{O}(1)$. Additionally it does have delete_at(idx) functionality.

• You mean you use an AVL tree or similar balanced tree? How do you make sure that removing the minimum does not cause more than constantly many rotations farther than constantly many steps away (from the removing site or the root)? In particular, removing elements from AVL trees can cause $O(\log n)$ rotations, so you need to argue how you prevent that. – Raphael Apr 22 '12 at 11:47
• What does "thread a binary search tree into an array" mean? – jbapple Apr 22 '12 at 15:25
• @AT: I share jbapple's sentiment. – Raphael Apr 22 '12 at 15:28
• Storing a binary tree in an array that way (like the classic binary heap) makes each rotation take $\Omega(k)$ time where $k$ is the size of the subtree rooted at the rotated node. In that case, doing "only" $O(1)$ rotations on an update still can take a long time. – jbapple Apr 22 '12 at 17:00
• Your update, in which you explain how to implement rotations in constant time, does not work in arrays. This answer is still incorrect. The Tarjan paper you reference is about trees stored with nodes and pointers. – jbapple Mar 16 '15 at 6:07

Find-min in $O(1)$ with expected update time of $O(\sqrt{log\text{ }log\text{ }n})$

See the 2007 paper: Equivalence between priority queues and sorting by Mikkel Thorup.

Note: He refers to the 2002 article by Han & Thorup: Integer Sorting in $O(n\text{ }\sqrt{log\text{ }log\text{ }n})$ Expected Time and Linear Space.

• Although the paper you linked is interesting, the priority queue they present does not have constant time deletions (if I read the abstract correctly), and hence is not what I'm asking for. – Alex ten Brink Apr 17 '12 at 14:58

## Analysis

Insert: $\mathcal{o}(n\ log\ log\ n)$

Search: $\mathcal{o}(log\ log\ n)$

Delete: $\mathcal{O}(1)$

Space: $\mathcal{O}(n)$

Get-Min: $\mathcal{O}(1)$

Extract-Min: $\mathcal{O}(1)$

## Implementation

1. Form a list out of an arbitrary (constant) number of elements, lets say 6: $\mathcal{O}(1)$
2. Sort the list: $\mathcal{O}(6)$=$\mathcal{O}(1)$
3. The insertion point for every subsequent node $k$, will be the second elements(') pos $\pm$ (-1 for <, +1 for > and with two args depends on which you start/finish at: $$((k > n_{\text{size}-1}) \lor (k<n_{0}) \lor ((k<n_{i}) \land (k>n_{i+1})))$$ and will be found using Dynamic Interpolation Search in: $\mathcal{o}(log\ log\ n)$

: Andersson, Arne, and Christer Mattsson. ‘Dynamic Interpolation Search in O(log log n) Time’. In Automata, Languages and Programming, edited by Andrzej Lingas, Rolf Karlsson, and Svante Carlsson, 700:15–27. Lecture Notes in Computer Science. Springer Berlin / Heidelberg, 1993. http://dx.doi.org/10.1007/3-540-56939-1_58.

• Well, the insert time is way off the mark. – Raphael May 19 '12 at 19:07
• This is way too sketchy. For example, what is $n_{size-1}$, $n_0$, $n_i$ and $n_{i+1}$? – Juho May 19 '12 at 20:51
• Reading the abstract of the paper you link, it seems these bounds are expected bounds for inputs of a particular distribution, which is therefore not what I'm looking for: I want the bounds I mention on any input. – Alex ten Brink May 19 '12 at 21:11
• @Raphael: No it isn't. mrm: positions in the list. AlextenBrink: It can easily be changed to $\mathcal{O}(log\ n)$ worst-case on any distribution using the Binary search algorithm to find your insertion point. – A T May 20 '12 at 3:05
• @AT Logarithmic binary search needs random access. What is the underlying list implemented as? You should really argue for your claimed bounds. Also, "positions in the list" is vague -- what positions and what do the symbols refer to? Not everyone has access to the paper you linked. Please try to make your answer (more) self-contained and at least summarize the facts. At this point I don't believe your answer is correct. – Juho May 20 '12 at 13:04