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

Question Detail: 

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.

Asked By : Alex ten Brink

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/524

Answered By : Raphael

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.