Binary heaps

LOG-HEAP UNION is an operation defined as the union of a binary heap of
size N with a binary heap of size log N. Can a binary heap support
LOG-HEAP UNION, INSERT and EXTRACT-MIN each in O(log N) time? I'm
interested in knowing whether this is (i) impossible (ii) non-trivial,
but (maybe) possible (iii) straightforward

Thanks,
Lauren

.

Relevant Pages

  • Re: Binary heaps
    ... > size N with a binary heap of size log N. Can a binary heap support ... > LOG-HEAP UNION, INSERT and EXTRACT-MIN each in Otime? ... It is this property that gives Tarjan's algorithm for Minimum Spanning ...
    (comp.theory)
  • Re: Binary heaps
    ... >> size N with a binary heap of size log N. Can a binary heap support ... > If there existed an algorithm that could do LOG-HEAP UNION on two ... > normal heaps as you ... then it could join any two heaps in linear time to ...
    (comp.theory)