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

Question

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.

Answer 1

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.

Answer 2

• 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.

Answer 3

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.

Answer 4

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.

Answer 5

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 [3]. 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.

[3]: Dietz, Paul F, and Rajeev Raman. ‘A Constant Update Time Finger Search Tree’. Information Processing Letters 52, no. 3 (1994): 147 – 154.

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[1].

[1]: Brodal, Gerth Stølting, George Lagogiannis, Christos Makris, Athanasios Tsakalidis, and Kostas Tsichlas. ‘Optimal Finger Search Trees in the Pointer Machine’. J. Comput. Syst. Sci. 67, no. 2 (September 2003): 381–418.

Answer 6

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.

Answer 7

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.

---

1 Patrascu, Mihai, and Erik D. Demaine. “Logarithmic Lower Bounds in the Cell-Probe Model.” SIAM J. Comput. 35, no. 4 (April 2006): 932–963. doi:10.1137/S0097539705447256.

Answer 8

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.

Answer 9

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[1] in: $\mathcal{o}(log\ log\ n)$

[1]: 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.