4
$\begingroup$

Is there anything in the literature on the following problem?:

Take a sequence of operations of Insert(element) and 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.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Is it fair to treat the output as the list of elements in the heap, without worrying about the structure of the heap? Or do we also need to predict the structure of the heap as well? $\endgroup$
    – D.W.
    Jul 24, 2018 at 6:50
  • $\begingroup$ Note that although @D.W.'s question might seem to be answered by "Where heaps are compared by which elements are in them" the situation is more subtle. Specifically, the first special case requires that the data structure returned by simulate can be constructed from an unordered list of its elements, so if simulate is supposed to return a heap then it requires a heap data structure such as a Fibonacci heap with $O(1)$ insertion. $\endgroup$
    – Peter Taylor
    Jul 24, 2018 at 9:02
  • $\begingroup$ I'm happy to eg return a bitmap of the elements in and out of the heap. You can heapify an unordered list in O(n). This doesn't require Fibonacci heaps. $\endgroup$
    – Matthias
    Jul 24, 2018 at 14:46

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.