<p>Is there anything in the literature on the following problem?:</p>

<p>Take a sequence of operations of <code>Insert(element)</code> and <code>PopMin</code> and apply them to an initially empty heap like this</p>

<pre><code>def run(seq):
  heap = empty()
  for op in seq:
    case op:
      Insert(x) -&gt; heap = insert(x, heap)
      PopMin -&gt; heap = popMin(heap)
  return heap
</code></pre>

<p>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 <code>simulate(seq) = run(seq)</code>? (Where heaps are compared by which elements are in them?)</p>

<p>Or alternatively, can we prove that such a simulation is not possible?</p>

<p>The only operation allowed one elements is comparison. (But I'm interested in results that make stronger assumption as well.)</p>

<p>I've looked through the literature and found a few special cases:</p>

<ul>
<li><p>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.</p></li>
<li><p>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.)</p></li>
<li><p>Solving the special case of repetitions of two inserts followed by a pop, is enough to solve the whole problem.</p></li>
<li><p>I have a linear time verification algorithm.</p></li>
<li><p>The problem is an instance of matroid optimization.</p></li>
</ul>

<p>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.</p>

CC BY-SA 4.0
2018-07-24T06:50:53.380Z
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?
D.W.
CC BY-SA 4.0
2018-07-24T09:02:50.220Z
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.
Peter Taylor
CC BY-SA 4.0
2018-07-24T14:46:02.910Z
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.
Matthias
<cc.complexity-theory><greedy-algorithms>
Simulate a heap in linear time
Matthias
# Simulate a heap in linear time

(Asked by: username_0 on 2018-07-24)

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.

**Tags:** cc.complexity-theory, greedy-algorithms
> **Comments:**
> **username_1**: 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?  
> **username_2**: 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.  
> **username_0**: 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.  

---

## 0 answers

