Is there anything in the literature on the following problem?:
Take a sequence of operations of
PopMin and apply them to an initially empty heap like this
def run(seq): heap = empty() for op in seq: case op: Insert(x) -> heap = insert(x, heap) PopMin -> heap = popMin(heap) return heap
We can naturally run the pseudo code above in O(n log n) time. Can we simulate their outcome in linear time in the number of operations, such that
simulate(seq) = run(seq)? (Where heaps are compared by which elements are in them?)
Or alternatively, can we prove that such a simulation is not possible?
The only operation allowed one elements is comparison. (But I'm interested in results that make stronger assumption as well.)
I've looked through the literature and found a few special cases:
If all inserts come before all pops, this reduces to finding quantiles of unsorted lists. Median-of-median algorithm can solve this in linear time.
If the elements to be inserted are the integers 1..n (but in arbitrary order), this is known as the offline minimum problem, and solvable in linear time with an offline variant of union-find. You can even get specific order elements for popped in. (Which you can not get in my version, otherwise a O(n log n) lower bound applies.)
Solving the special case of repetitions of two inserts followed by a pop, is enough to solve the whole problem.
I have a linear time verification algorithm.
The problem is an instance of matroid optimization.
I have a candidate algorithm using soft heaps that might work in linear time, but I haven't proven it yet. I also imagine that a random sampling scheme might work and be more elementary than soft heaps, but so far the math of analysing it has proven too much for me.
simulatecan be constructed from an unordered list of its elements, so if
simulateis supposed to return a heap then it requires a heap data structure such as a Fibonacci heap with $O(1)$ insertion. $\endgroup$