Re: Binary heaps

lauren wrote:
> 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

I'm guessing that you mean the first heap is of size N and the other
O(log N) ? If you mean exactly log N, then don't read the rest of this
post :).

If there existed an algorithm that could do LOG-HEAP UNION on two
normal heaps (by normal I mean without any modifications) as you
describe it, then it could join any two heaps in linear time to
their size.

We have 2 heaps, of size N and M.
We know that M=O(log N)

We have an algorithm that joins them in O(log N) time.
Let's say it's O(log N) + O(f(M)), where f(n)=O(n).

So if we forget that M=O(log N) and give this algorithm two
heaps of equal size, it will join them in linear time.

ps.: there might be a mistake in my reasoning, I'm not very
experienced in this subject.

.

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? ... There are only Osuch cells. ...
    (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)
  • Re: Advice on data structure for scheduled events
    ... putting each event into an appropriate bucket (that holds all events ... strategy (for a naive vector, adding a new element occassionally takes ... What sort of heap? ... Googmeister suggested a binary heap, ...
    (comp.programming)
  • Re: Proof that this assertion about heaps is true
    ... assuming the particular implementation is a binary heap and the ... I suppose to guarantee I am okay I'll have to write my own heap ... >> will definitly restore the heap by definition. ... > the requirements of the standard. ...
    (comp.theory)
  • Re: Some basic interview-type questions
    ... linear time (assuming "swapping down" elements is in O(1)). ... insight is that when you build the heap bottom-up and have k levels, ...
    (comp.programming)